Submission #249495

#	Time	Username	Problem	Language	Result	Execution time	Memory
249495		VEGAnn	Poklon (COCI17_poklon7)	C++14	114 / 120	664 ms	262148 KiB

poklon

#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 / 120