Submission #491803

#TimeUsernameProblemLanguageResultExecution timeMemory
491803Vladth11Poklon (COCI17_poklon7)C++14
0 / 120
1102 ms172460 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered; const ll NMAX = 2000001; const ll nr_of_bits = 17; const ll MOD = 1000000007; const ll INF = (1LL << 59); int frunza[NMAX], val[NMAX]; vector <int> v[NMAX]; int cnt, n, maxim = 0; void addEdge(ll a, ll b){ if(a < 0){ val[++cnt] = -a; a = cnt; frunza[a] = 1; } v[a].push_back(b); v[b].push_back(a); } int lvl[NMAX]; int maxi = 0; void DFS(int node, int p){ lvl[node] = lvl[p] + 1; maxi = max(maxi, lvl[node]); for(auto x : v[node]){ if(x != p){ DFS(x, node); } } } int fa(int x, int zero){ int init = zero; for(int i = 0; i <= 30 && zero; i++){ if(x & (1LL << i)) break; zero--; } if(zero == 0){ while(init--) x /= 2; return x; } int nr = 0; for(int i = 0; i <= 30; i++){ if(i < init){ continue; } nr += (1LL << i); } for(int i = 30; i >= init; i--){ if(nr - (1LL << i) >= x){ nr -= (1LL << i); } } while(init--) nr /= 2; return nr; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll i; cin >> n; cnt = n; for(i = 1; i <= n; i++){ int x, y; cin >> x >> y; addEdge(x, i); addEdge(y, i); } DFS(1, 0); for(i = 1; i <= cnt; i++){ if(!frunza[i]) continue; maxim = max(maxim, fa(val[i], maxi - lvl[i] - 1)); } int ok = 0; int last = 0; for(int i = 30; i >= 0; i--){ if(maxim & (1LL << i)){ ok = 1; last = 0; cout << 1; }else if(ok){ last++; cout << 0; } } for(i = 1; i < maxi; i++) cout << 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...