Submission #249489

# Submission time Handle Problem Language Result Execution time Memory
249489 2020-07-15T06:48:50 Z VEGAnn Poklon (COCI17_poklon7) C++14
114 / 120
589 ms 262148 KB
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
using namespace std;
const int N = 1000100;
int lf[N], rt[N], n;

vector<bool> calc(int pos){
    vector<bool> l, r;

    if (lf[pos] < 0){
        int vl = -lf[pos];
        l.clear();

        while (vl > 0){
            l.PB((vl & 1));
            vl >>= 1;
        }

        reverse(all(l));
    } else l = calc(lf[pos]);

    if (rt[pos] < 0){
        int vl = -rt[pos];
        r.clear();

        while (vl > 0){
            r.PB((vl & 1));
            vl >>= 1;
        }

        reverse(all(r));
    } else r = calc(rt[pos]);

    if (sz(r) == sz(l)){
        bool fi = 1;

        for (int i = 0; i < sz(l) && fi; i++){
            if (r[i] == l[i]) continue;

            if (l[i] < r[i]) fi = 0;

            break;
        }

        if (fi){
            l.PB(0);
            return l;
        } else {
            r.PB(0);
            return r;
        }
    } else if (sz(r) > sz(l)){
        r.PB(0);
        return r;
    } else {
        l.PB(0);
        return l;
    }
}

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];

    vector<bool> res = calc(1);

    for (int cr : res)
        cout << cr;

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 7 ms 2432 KB Output is correct
12 Correct 8 ms 1920 KB Output is correct
13 Correct 36 ms 11136 KB Output is correct
14 Correct 69 ms 23032 KB Output is correct
15 Correct 53 ms 1208 KB Output is correct
16 Correct 225 ms 55416 KB Output is correct
17 Correct 508 ms 114040 KB Output is correct
18 Correct 524 ms 132344 KB Output is correct
19 Correct 589 ms 82424 KB Output is correct
20 Runtime error 384 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)