oj.uz

Submission #249502

# Submission time Handle Problem Language Result Execution time Memory
249502 2020-07-15T07:14:12 Z VEGAnn Poklon (COCI17_poklon7) C++14
120 / 120
 654 ms 233304 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#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 34 ms 62968 KB Output is correct
2 Correct 34 ms 63028 KB Output is correct
3 Correct 41 ms 62968 KB Output is correct
4 Correct 34 ms 62976 KB Output is correct
5 Correct 34 ms 62968 KB Output is correct
6 Correct 34 ms 63104 KB Output is correct
7 Correct 34 ms 62968 KB Output is correct
8 Correct 34 ms 62976 KB Output is correct
9 Correct 34 ms 62968 KB Output is correct
10 Correct 34 ms 62976 KB Output is correct
11 Correct 40 ms 64120 KB Output is correct
12 Correct 41 ms 64120 KB Output is correct
13 Correct 68 ms 69112 KB Output is correct
14 Correct 94 ms 75256 KB Output is correct
15 Correct 91 ms 69624 KB Output is correct
16 Correct 241 ms 98808 KB Output is correct
17 Correct 519 ms 143192 KB Output is correct
18 Correct 552 ms 148480 KB Output is correct
19 Correct 654 ms 147960 KB Output is correct
20 Correct 621 ms 233304 KB Output is correct