Luogu 2783 有机化学之神偶尔会做作弊

去年NOIP之前做的,人生中第一道黑题,真是可喜可贺可喜可贺(虽然参考了题解)
Tarjan缩点重新构图,然后统计题目给定两点的树上距离即可。
上代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
using namespace std;

//define
const int maxn=1e4+5;
const int maxm=5e4+5;

struct Edge{ int v,next; }e[maxm*2],e2[maxm*2];
int head[maxn],dfn[maxn],low[maxn],visx,head2[maxn],tot,fa[maxn][25],belong[maxn],m,n,tot2,dep[maxn],xx[maxm],yy[maxm];
bool exist[maxn];
stack<int> st;

inline void addedge(int u,int v){
    e[++tot].v=v;e[tot].next=head[u];head[u]=tot;
}
int cnt;
void tj(int u,int from){
    low[u]=dfn[u]= ++visx; st.push(u); exist[u]=true;
    for(register int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==from) continue;
        if(dfn[v]==-1) tj(v,u),low[u]=min(low[u],low[v]);
        else if(exist[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++cnt;
        while(1){
            int v=st.top();st.pop();
            exist[v]=0; belong[v]=cnt;
            if(v==u) break;
        }
    }
}

inline void addedge2(int u,int v){
    e2[++tot2].v=v;e2[tot2].next=head2[u];head2[u]=tot2;
}

void dfs(int u,int from,int deepth){
    dep[u]=deepth; fa[u][0]=from;
    for(register int i=head2[u];i;i=e2[i].next){
        int v=e2[i].v;
        if(v!=from) dfs(v,u,deepth+1);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(register int j=0;j<=22;j++)
        if((dep[u]-dep[v])&(1<<j)) u=fa[u][j];
    if(u==v) return u;
    for(register int i=22;i>=0;i--)
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i],v=fa[v][i];
        }
    return fa[u][0];
}

int ans[28000];
int change(int n){
    int cur=0;
    if(n==0){ cout<<'0';return 0; }
    if(n<0) { putchar('-');n=0-n; }
    while(n){
        ans[++cur]=n%2;n/=2;
    }
    for(register int i=cur;i>=1;i--) cout<<ans[i];
    cout<<endl;
}

int main(){
    cin>>n>>m;
    memset(dfn,-1,sizeof dfn );
    memset(low,-1,sizeof low );
    for(register int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        xx[i]=u,yy[i]=v;
        addedge(u,v),addedge(v,u);
    }
    for(register int i=1;i<=n;i++)
        if(dfn[i]==-1)
            tj(i,-1);
    for(register int i=1;i<=m;i++){
        if(belong[xx[i]]!=belong[yy[i]]){
            addedge2(belong[xx[i]],belong[yy[i]]);
            addedge2(belong[yy[i]],belong[xx[i]]);
        }
    }
    dfs(belong[1],belong[1],0);
    for(register int j=1;j<=22;j++)
        for(register int i=1;i<=cnt;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    int T;cin>>T;
    while(T--){
        int u,v;cin>>u>>v;
        int ans=lca(belong[u],belong[v]);
        change(dep[belong[u]]+dep[belong[v]]-dep[ans]-dep[ans]+1);//二进制格式输入距离
    }
    return 0;
}
Tags:OI图论TarjanLCA
上一篇
下一篇

添加新评论