oj.uz

Submission #249498

# Submission time Handle Problem Language Result Execution time Memory
249498 2020-07-15T07:01:04 Z VEGAnn Poklon (COCI17_poklon7) C++14
120 / 120
 639 ms 201948 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 1000100;
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 17 ms 31616 KB Output is correct
2 Correct 17 ms 31616 KB Output is correct
3 Correct 16 ms 31616 KB Output is correct
4 Correct 16 ms 31616 KB Output is correct
5 Correct 18 ms 31648 KB Output is correct
6 Correct 17 ms 31744 KB Output is correct
7 Correct 16 ms 31616 KB Output is correct
8 Correct 17 ms 31616 KB Output is correct
9 Correct 17 ms 31744 KB Output is correct
10 Correct 17 ms 31792 KB Output is correct
11 Correct 23 ms 32888 KB Output is correct
12 Correct 25 ms 32896 KB Output is correct
13 Correct 48 ms 37624 KB Output is correct
14 Correct 85 ms 43896 KB Output is correct
15 Correct 76 ms 38264 KB Output is correct
16 Correct 228 ms 67704 KB Output is correct
17 Correct 514 ms 111748 KB Output is correct
18 Correct 522 ms 117216 KB Output is correct
19 Correct 628 ms 116600 KB Output is correct
20 Correct 639 ms 201948 KB Output is correct