Submission #491697

#TimeUsernameProblemLanguageResultExecution timeMemory
491697Vladth11Poklon (COCI17_poklon7)C++14
78 / 120
1104 ms235052 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 << " " #pragma GCC optimize("Ofast", "unroll-loops") #pragma GCC target("sse", "sse2", "avx") 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); ll val[NMAX], frunza[NMAX]; vector <int> v[NMAX]; ll 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){ ll maximm = val[node]; lvl[node] = lvl[p] + 1; maxi = max(maxi, lvl[node]); ll fii = 0; for(auto x : v[node]){ if(x != p){ fii++; DFS(x, node); maximm = max(maximm, val[x]); } } val[node] = max(1LL, fii) * maximm; } ll fa(ll x, ll zero){ ll 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; } ll nr = 0; for(int i = 0; i <= 60; i++){ if(i < init){ continue; } nr += (1LL << i); } for(int i = 60; 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])); } int ok = 0; int last = 0; for(int i = 60; 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...