oj.uz

Submission #249495

# Submission time Handle Problem Language Result Execution time Memory
249495 2020-07-15T06:59:24 Z VEGAnn Poklon (COCI17_poklon7) C++14
114 / 120
 664 ms 262148 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
const int N = 3000100;
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 = n;

    int res = calc(1);

    cout << s[res];

    return 0;
}

Subtask #1
114.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94328 KB Output is correct
2 Correct 48 ms 94336 KB Output is correct
3 Correct 47 ms 94328 KB Output is correct
4 Correct 47 ms 94316 KB Output is correct
5 Correct 47 ms 94328 KB Output is correct
6 Correct 47 ms 94328 KB Output is correct
7 Correct 48 ms 94328 KB Output is correct
8 Correct 47 ms 94324 KB Output is correct
9 Correct 47 ms 94328 KB Output is correct
10 Correct 47 ms 94328 KB Output is correct
11 Correct 53 ms 95480 KB Output is correct
12 Correct 54 ms 95480 KB Output is correct
13 Correct 79 ms 100344 KB Output is correct
14 Correct 106 ms 106488 KB Output is correct
15 Correct 106 ms 100856 KB Output is correct
16 Correct 261 ms 130296 KB Output is correct
17 Correct 552 ms 174600 KB Output is correct
18 Correct 570 ms 179716 KB Output is correct
19 Correct 664 ms 179320 KB Output is correct
20 Runtime error 634 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)