제출 #249489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249489		VEGAnn	Poklon (COCI17_poklon7)	C++14	114 / 120	589 ms	262148 KiB

poklon

#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;
}

• Subtask 1: 114 / 120