Bài C - Codeforces Round #543 (Div. 2)

Bài C:
Đề bài: Sasha đang tham gia một cuộc thi lập trình. Trong một các vấn đề, cô ấy phải kiểm tra liệu rằng một vài rễ cây có phải isomorphic hay không. Cô ấy chưa bao giờ nhìn thấy vấn đề này trước đó, nhưng, là một thí sinh có kinh nghiệm, cô ấy đoán rằng cố ấy nên nối các cây với một vài dãy và sau đó so sánh các dãy này thay vì các cây. Sasha muốn nỗi mỗi cây với một dãy a(0),a(1),...,a(h) trong đó h là chiều cao của cây, và a(i) bằng số các đỉnh mà nằm tại khoảng cách của cạnh i từ rễ.
 Không may mắn thay, vào lúc này trực giác (intuition) đã bị sai, và có thể có một vài cây nối cùng một dãy. Để chứng minh điều này, bạn cần viết một chương trình , cho một chuỗi a(i), xây dựng hai cây có rễ không hẻo lánh mà nối các dãy này, hoặc xác định rằng chỉ có 1 cái cây như vậy.
  Hai cây có rễ được gọi là hẻo lánh, nếu bạn có thể tái hiện (reenumerate) các đỉnh của cây đầu tiên theo cách này, có nghĩa là chỉ số của rễ trở nên bằng chỉ số của rễ cây thứ hai, và hai cây này trở nên bằng nhau.
 Chiều cao của một cây có rễ là số cạnh lớn nhất trên đường đi từ rễ đến các đỉnh khác bất kỳ.
Đầu vào:
+ Dòng đầu tiên chứa một số nguyên h(2<=h<=10^5) - là chiều cao của cây.
+ Dòng thứ hai chứ h+1 số nguyên - một dãy a(0),a(1),...,a(h)(1<=a(i)<=2.10^5). Tổng của tất cả các a(i) không vượt quá 2.10^5. Nó đảm bảo rằng có ít nhất một cây nối dãy này.
Đầu ra:
+ Nếu chỉ có một cây nối dãy này, in ra 'perfect'
+Ngược lại, in 'ambiguous' ở dòng đầu tiên.
Dòng thứ hai và dòng thứ ba in ra mô tả hai cây theo dạng sau:
- Một dòng in (a(0)+a(1)+...+a(h)), phần tử thứ k của chúng có thể là bố mẹ đỉnh k hoặc cùng bằng 0, nếu đỉnh k là rễ.
Những cái cây này không hẻo lánh và nối với dãy đã cho.
Ví dụ:
Đầu vào:
2
1 1 1
Đầu ra:
perfect
/***/
Đầu vào:
2
1 2 2
Đầu ra:
ambiguous
0 1 1 3 2
0 1 1 3 2
Chú ý:
Chỉ có một cây ở ví dụ đầu tiên và hai cây được in từ ví dụ 2 được biểu diễn như các hình dưới đây.

Hướng dẫn: Có rất nhiều cách để giải bài toán này. Việc đầu tiên chúng ta xây dựng một cây đơn bất kì. Để làm việc này, chúng ta đầu tiên xây dựng đường đi dài nhất từ rễ và sau đó đính kèm đính kèm vào những đỉnh duy trì một chiều cao thích hợp. Vì vậy mỗi đỉnh hoặc là đường đi dài nhất hoặc có bố mẹ trên đường này. Để xây dựng cây thứ hai bạn nên sử dụng những đỉnh khác nhau từ bậc trước trong suốt việc xây dựng để tạo ra nó khác với cây đầu tiên. Điều này luôn luôn có thể nếu có hai a(i) liên tiếp >1. Mặt khác cây được xác định độc nhất bởi dãy a(i).
Lời giải:

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],m[200005],i=0;
int main(){
 cin>>n;
 while(i<=n) cin>>a[i++];
 for(i=0;i<n;i++) if(a[i]>1 && a[i+1]>1){
  cout<<"ambiguous\n";
  int l=0,k=0,t;
  for(int j=0; j<=n; j++){
   while(a[j]--) m[k++]=l;
   l=k;
   if(j==i) t=k;
  }
  l=2;
  while(l--){
   for(int j=0; j<k; j++) cout<<((j)? " ":"")<<((j==t && l)? m[j]-1:m[j]);
   cout<<"\n"; 
  }
  return 0;
 }
 cout<<"perfect\n";
}