Codeforces #453 Div1 A. Hashing Trees

そこそこの順位でレートが回復したのはよかった。
http://codeforces.com/contest/901/problem/A

問題

根付き木に各深さにおいて、頂点がいくつあるかが与えられる。
この情報から構成される木はすべてisomorphicか、そうでないか判定せよ。

解法

どこか連続する深さにおいて、両方とも２つ以上頂点があればisomorphicにならない。
片方の木では深い方の頂点の親を１頂点に寄らせ、もう片方では複数頂点に散らせばよい。

int H;
int A[202020];
int P[201010];
int S[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H;
	int p=0;
	int cur=1;
	FOR(i,H+1) {
		S[i]=cur;
		cin>>A[i];
		FOR(j,A[i]) P[cur++]=p;
		p=cur-1;
	}
	FOR(i,H) if(A[i]>1 && A[i+1]>1) {
		cout<<"ambiguous"<<endl;
		for(j=1;j<cur;j++) {
			if(j>1) cout<<" ";
			cout<<P[j];
		}
		cout<<endl;
		P[S[i+1]]--;
		for(j=1;j<cur;j++) {
			if(j>1) cout<<" ";
			cout<<P[j];
		}
		cout<<endl;
		return;
	}
	cout<<"perfect"<<endl;
	
	
}

まとめ

まぁこれはすんなり。