Submission #577694

#TimeUsernameProblemLanguageResultExecution timeMemory
577694GioChkhaidzePoklon (COCI17_poklon7)C++14
96 / 120
311 ms238592 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> #define f first #define s second using namespace std; const int N = 1e6 + 6; int n, lf[N], rf[N], c[N]; pair < int , pair < int , int > > dfs(int x) { if (x > n) { int sz = (int)log2(c[x]) + 1; return {c[x], {sz, sz}}; } pair < int , pair < int , int > > Lf = dfs(lf[x]); pair < int , pair < int , int > > Rf = dfs(rf[x]); ++Lf.s.f, ++Rf.s.f; if (Lf.s.f > Rf.s.f) return Lf; if (Lf.s.f < Rf.s.f) return Rf; if (Lf.s.s < Rf.s.s) { if (Lf.f * (1 << (Rf.s.s - Lf.s.s)) > Rf.f) return Lf; return Rf; } if (Lf.s.s > Rf.s.s) { if (Rf.f * (1 << (Lf.s.s - Rf.s.s)) > Lf.f) return Rf; return Lf; } if (Lf.f > Rf.f) return Lf; return Rf; } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; int ts = n; for (int i = 1; i <= n; ++i) { cin >> lf[i] >> rf[i]; if (lf[i] < 0) { ++ts; c[ts] = -lf[i]; lf[i] = ts; } if (rf[i] < 0) { ++ts; c[ts] = -rf[i]; rf[i] = ts; } } pair < int , pair < int , int > > ans = dfs(1); for (int i = ans.s.s - 1; i >= 0; --i) { cout << ((ans.f >> i) & 1); } for (int i = 0; i < ans.s.f - ans.s.s; ++i) { cout << 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...