poj1988cube_stacking

2488 ワード

相変わらずコレクションを調べています...でも...この問題は一晩中出てこなかった.
本来は非圧縮状態で実現しようとしていたが,タイムアウトし,また各点の直接親ノードを介して導出しようとした結果,自分の推定式が間違っていることに気づいた.
この道は通じなくて、本当に耐えられなくて标程を探しました...あなたの妹の
各関数はすべてスレッドの机能に変えて、意外にも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;
}

涙が零れる...邪魔しないで