poj1988cube_stacking
相変わらずコレクションを調べています...でも...この問題は一晩中出てこなかった.
本来は非圧縮状態で実現しようとしていたが,タイムアウトし,また各点の直接親ノードを介して導出しようとした結果,自分の推定式が間違っていることに気づいた.
この道は通じなくて、本当に耐えられなくて标程を探しました...あなたの妹の
各関数はすべてスレッドの机能に変えて、意外にもwa、各位に大いにわだかまりを探してもらいます...
先標程
そして私自身です...
涙が零れる...邪魔しないで
本来は非圧縮状態で実現しようとしていたが,タイムアウトし,また各点の直接親ノードを介して導出しようとした結果,自分の推定式が間違っていることに気づいた.
この道は通じなくて、本当に耐えられなくて标程を探しました...あなたの妹の
各関数はすべてスレッドの机能に変えて、意外にもwa、各位に大いにわだかまりを探してもらいます...
先標程
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
int up,count,parent;
};
node Cu[30001];
void creat(){
int c;
for(c=0;c<=30000;c++){
Cu[c].count=1;
Cu[c].parent=c;
Cu[c].up=0;
}
}
int find_set(int i){
int t=Cu[i].parent;
if(t!=i){
Cu[i].parent=find_set(t);
Cu[i].up+=Cu[t].up;
}
return Cu[i].parent;
}
void uion(int i,int j){
int x=find_set(i);
int y=find_set(j);
Cu[y].parent=x;
Cu[y].up=Cu[x].count;
Cu[x].count+=Cu[y].count;
}
int main(){
creat();
int n,a,b;
char s;
cin>>n;
while(n--){
cin>>s;
if(s=='M'){
scanf("%d %d",&a,&b);
uion(a,b);
}
else if(s=='C'){
scanf("%d",&a);
b=find_set(a);
printf("%d
",Cu[b].count-Cu[a].up-1);
}
}
return 0;
}
そして私自身です...
#include<iostream>
#include<cstdio>
using namespace std;
int x,y,p,sets[50000],val[50000],up[50000];
char c;
//bool flag[50000];
int find(int x){
int y=sets[x];
if(sets[x]==x) return x;
else{
up[x]+=up[y];
y=find(sets[x]);
sets[x]=y;
return y;
}
}
void move(int x,int y){
int a,b;
a=find(x);
b=find(y);
//cout<<"moves "<<a<<" to "<<b<<endl;
//flag[a]=true;
sets[b]=a;
up[b]=val[a];
val[a]+=val[b];
}
int cnt(int x){
int y=find(x);
cout<<val[y]-up[x]-1<<endl;
}
int main(){
for(int i=0;i<50000;i++){
sets[i]=i;
val[i]=1;
up[i]=0;
//flag[i]=false;
}
scanf("%d",&p);
while(p--){
/*for(int i=1;i<=6;i++)
cout<<i<<"belong to"<<sets[i]<<" val="<<val[i]<<" UP="<<up[i]<<endl;
cout<<endl;*/
//cout<<p<<endl;
getchar();
scanf("%c",&c);
if(c=='C'){
scanf("%d",&x);
cnt(x);
}
else if(c=='M'){
scanf("%d%d",&x,&y);
move(x,y);
}
}
return 0;
}
涙が零れる...邪魔しないで