oj.uz

Submission #249497

# Submission time Handle Problem Language Result Execution time Memory
249497 2020-07-15T07:00:30 Z VEGAnn Poklon (COCI17_poklon7) C++14
120 / 120
 642 ms 233436 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 2000100;
string s[N];
int lf[N], rt[N], n, ind[N], last;

int calc(int pos){
    int il = -1, ir = -1;

    if (lf[pos] > 0)
        il = calc(lf[pos]);

    if (rt[pos] > 0)
        ir = calc(rt[pos]);

    if (il < 0){
        il = ++last;

        int vl = -lf[pos];
        s[il] = "";

        while (vl > 0){
            s[il] += char((vl & 1) + '0');
            vl >>= 1;
        }

        reverse(all(s[il]));
    }

    if (ir < 0){
        ir = ++last;

        int vl = -rt[pos];
        s[ir] = "";

        while (vl > 0){
            s[ir] += char((vl & 1) + '0');
            vl >>= 1;
        }

        reverse(all(s[ir]));
    }

    // индексы >n перезаписывать

    if (sz(s[ir]) == sz(s[il])){
        bool fi = 1;

        for (int i = 0; i < sz(s[il]) && fi; i++){
            if (s[ir][i] == s[il][i]) continue;

            if (s[il][i] < s[ir][i]) fi = 0;

            break;
        }

        if (fi){
            ind[pos] = il;
            s[il] += "0";
            return il;
        } else {
            ind[pos] = ir;
            s[ir] += "0";
            return ir;
        }
    } else if (sz(s[ir]) > sz(s[il])){
        ind[pos] = ir;
        s[ir] += "0";
        return ir;
    } else {
        ind[pos] = il;
        s[il] += "0";
        return il;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> lf[i] >> rt[i];

    last = 0;

    int res = calc(1);

    cout << s[res];

    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62968 KB Output is correct
2 Correct 32 ms 62968 KB Output is correct
3 Correct 33 ms 62968 KB Output is correct
4 Correct 32 ms 62968 KB Output is correct
5 Correct 33 ms 62968 KB Output is correct
6 Correct 32 ms 62968 KB Output is correct
7 Correct 33 ms 62976 KB Output is correct
8 Correct 32 ms 62976 KB Output is correct
9 Correct 33 ms 62968 KB Output is correct
10 Correct 33 ms 63096 KB Output is correct
11 Correct 39 ms 64128 KB Output is correct
12 Correct 39 ms 64120 KB Output is correct
13 Correct 65 ms 68984 KB Output is correct
14 Correct 94 ms 75256 KB Output is correct
15 Correct 93 ms 69624 KB Output is correct
16 Correct 241 ms 98808 KB Output is correct
17 Correct 541 ms 143108 KB Output is correct
18 Correct 536 ms 148484 KB Output is correct
19 Correct 642 ms 148028 KB Output is correct
20 Correct 640 ms 233436 KB Output is correct