Codeforces #453 Div2C

Codeforces #453 Div2C Hashing Trees

根つき木を,高さiの頂点がいくつあるかをa[i]と対応させることをかんがえる.配列aが与えられる.この配列に対応する木が一つにかぎられるかどうかを判定せよ.二つ以上存在するときは,そのような木を二つ構成せよ.

a[i]>1かつa[i+1]>1となるようなiが存在するときは,高さi+1の頂点を高さiの頂点のどれに割り振るかで異なる二つの木が作れる.逆に全てのiについてa[i]≦1またはa[i+1]≦1のときは明らかに一通りの木しかない.構成は適当に頑張る.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int a[100000];
int par1[200000];
int par2[200000];
int main() {
    int h;
    cin >> h;
    for (int i = 0; i < h + 1; i++) cin >> a[i];
    bool ok = 1;
    for (int i = 1; i < h + 1; i++) {
        if (a[i - 1] > 1 && a[i] > 1) {
            ok = 0;
            break;
        }
    }
    if (ok) {
        cout << "perfect" << endl;
        return 0;
    }
    par1[0] = 0;
    int idx = 1;
    for (int i = 1; i < h + 1; i++) {
        int p = idx;
        for (int j = 0; j < a[i]; j++) par1[idx++] = p;
    }
    par2[0] = 0;
    idx = 1;
    for (int i = 1; i < h + 1; i++) {
        if (a[i - 1] > 1 && a[i] > 1) {
            int p1 = idx;
            int p2 = idx - 1;
            for (int j = 0; j < a[i] - 1; j++) par2[idx++] = p1;
            par2[idx++] = p2;
        }
        else {
            int p = idx;
            for (int j = 0; j < a[i]; j++) par2[idx++] = p;
        }
    }
    cout << "ambiguous" << endl;
    cout << par1[0];
    for (int i = 1; i < idx; i++) cout << " " << par1[i];
    cout << endl;
    cout << par2[0];
    for (int i = 1; i < idx; i++) cout << " " << par2[i];
    cout << endl;
}