CF1804F

n点m边无向图，新加q条边。n,m,q<=1e5

RE了。但是只把存边数组e的大小从 4N 改为 8N 就对了。为什么。

#include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x){
    x=0;int sgn=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')sgn=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=sgn;
}
template<typename T,typename ...Args>
void read(T &x,Args &...rest){read(x);read(rest...);}
constexpr int N=1e5+5;
struct edge{int to,nx,t;}e[8*N];
int head[N],tot=1;
void add_edge(int u,int v,int t){
    e[++tot]={v,head[u],t};
    head[u]=tot;
}
#define repg(i,u,v) for(int i=head[u],v=e[i].to;i;i=e[i].nx,v=e[i].to)
bool vis[N];
int dis[N],n,m,q;
int getans(int lim){
    queue<int> Q;
    Q.push(1);
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    dis[1]=0;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        repg(i,u,v){
            if(e[i].t>lim||vis[v])continue;
            dis[v]=dis[u]+1;
            vis[v]=1;
            Q.push(v);
        }
        if(Q.empty())return dis[u];
    }
    throw 114514;
}
bool check(int cur,int k){
    int cp=getans(k);
    return cur>2*cp;
}
int main(){
    read(n,m,q);
    for(int i=1,u,v;i<=m;i++){
        read(u,v);
        add_edge(u,v,0);
        add_edge(v,u,0);
    }
    for(int i=1,u,v;i<=q;i++){
        read(u,v);
        add_edge(u,v,i);
        add_edge(v,u,i);
    }
    for(int i=0;i<=q;){
        int l=i+1,r=q,mid,res=q+1,ans;
        try{ans=getans(i);}
        catch(int int_err){cerr<<"ERROR114514!!!"<<endl;return 0;}
        while(l<=r){
            mid=l+r>>1;
            if(check(ans,mid))r=mid-1,res=mid;
            else l=mid+1;            
        }
        for(int j=i;j<res;j++)printf("%d ",ans);
        i=res;
    }
    return 0;
}