社区讨论

0分,合不起来求调

P1196[NOI2002] 银河英雄传说参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhjlb1nr
此快照首次捕获于
2025/11/04 04:25
4 个月前
此快照最后确认于
2025/11/04 04:25
4 个月前
查看原帖
R T
CPP
#include<bits/stdc++.h>
using namespace std;
int fa[30003],son[30003],dep[30003];
vector<int> siz(30003,1);
int findf(int x){
    if(fa[x]==x)return x;
    return fa[x];
}
int finds(int x){
    if(son[x]==x)return x;
    return son[x];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=30002;i++){
        fa[i]=i;
        son[i]=i;
    }
    for(int i=1;i<=n;i++){
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M'&&findf(a)!=findf(b)){
            // cout<<i<<'\n';
            int k=finds(a);
            do{
                dep[k]+=siz[findf(b)];
                k=fa[k];
            }while(k!=fa[k]);
            siz[findf(b)]+=siz[findf(a)];
            fa[findf(a)]=finds(b);
            son[finds(b)]=findf(a);
        }
        if(c=='C'){
            // cout<<findf(a)<<" "<<findf(b);
            if(findf(a)!=findf(b)){
                cout<<-1<<'\n';
                continue;
            }
            cout<<abs(dep[a]-dep[b])-1<<'\n';
        }
    }
}
/*
g++ p2606.cpp -o 2606
./2606

*/

回复

1 条回复,欢迎继续交流。

正在加载回复...