模拟题千万不要复制粘贴

模拟测试74

set不可重,multiset

模拟测试87

暴力和(伪)正解犯的同一个sb错误0分

不要过于相信对拍

模拟测试87改题

不开multiset见祖宗

(一场挂100)*2

又是过于相信对拍

暴力要重码不要在你打的正解基础上改

模拟测试94

炸内存了

100挂成0

没事不要全开long long

注意空间,

打模拟对拍如果方便重构可以再打一遍,第一遍拍第二遍

少清空一个r

这种错误还在犯

倒是避免了多测不清空………………………………………………..

WA0代码

AC代码

正解挂成0

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 610000
ll head[A],ver[A],nxt[A],edg[A],maxx[A][21],f[A][21],fa[A],dep[A];
ll t,tot,n,m,q;
struct node{
    ll x,y,z;
    friend bool operator < (const node &a,const node &b){
        return a.z<b.z;
    }
}e[A];
ll find(ll x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void add(ll x,ll y,ll z){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;edg[tot]=z;
}
void merge(ll x,ll y){
    x=find(x),y=find(y);
    if(x!=y){
        fa[x]=y;
    }
}
ll lca(ll x,ll y){
    ll maxn=0;
    if(dep[x]>dep[y]) swap(x,y);
    for(ll i=t;i>=0;i--){
        if(dep[x]<=dep[f[y][i]]){
            maxn=max(maxn,maxx[y][i]);
            y=f[y][i];
        }
        if(dep[x]==dep[y]) break;
    }
    if(x==y) return maxn;
    for(ll i=t;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            maxn=max(maxn,maxx[x][i]);
            maxn=max(maxn,maxx[y][i]);
            x=f[x][i],y=f[y][i];
        }
    }
    return maxn;
}
void dfs(ll x,ll pre){
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        f[y][0]=x;
        maxx[y][0]=edg[i];
        dep[y]=dep[x]+1;
        dfs(y,x);
    }
}
int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&q);
    t=log(n)/log(2)+1;
    for(ll i=1;i<=n;i++) fa[i]=i;
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].z);
    }
    sort(e+1,e+m+1);
    for(ll i=1;i<=m;i++){
        ll x=e[i].x,y=e[i].y;
        x=find(x),y=find(y);
        if(x!=y){
            merge(x,y);
            add(e[i].x,e[i].y,e[i].z);
            add(e[i].y,e[i].x,e[i].z);
        }
    }
    f[1][0]=1;dfs(1,0);
    for(ll j=1;j<=t;j++){
        for(ll i=1;i<=n;i++){
            ll now=f[i][j-1];
            f[i][j]=f[now][j-1];
            maxx[i][j]=max(maxx[now][j-1],maxx[i][j-1]);
        }
    }
    for(ll i=1;i<=q;i++){
        ll x,y,xx,yy;
        scanf("%lld%lld",&x,&y);
        if(find(x)!=find(y)){
            printf("-1\n");
        }
        else {
            printf("%lld\n",lca(x,y));
        }
    }
}

View Code

倍增一定要注意直接与lca相连的边

如果对拍不了一定要静态查错

cnt写成n，