#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
vector<vector<int>> g;
vector<int> v;
void dfs(int k, int p){
for(int y = 0; y < g[k].size(); y++){
dfs(g[k][y], k);
}
if(p == -1) return;
v[p] = max(v[k]+1, v[p]);
}
void dfs1(int k){
for(int y = 0; y < g[k].size(); y++){
v[g[k][y]] = v[k]-1;
dfs1(g[k][y]);
}
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
g.resize(n+1);
v.resize(n+1);
vector<int> b(n+1);
vector<vector<int>> sv(n+1);
for(int i = 1; i <= n; i++){
int a, b; cin >> a >> b;
if(a > 0){
g[i].push_back(a);
}else{
sv[i].push_back(abs(a));
}
if(b > 0){
g[i].push_back(b);
}else{
sv[i].push_back(abs(b));
}
}
dfs(1, -1);
dfs1(1);
int low = 0;
int top = 1e9;
int ans = 0;
vector<int> p(32);
int c = 1;
for(int y = 0; y <= 31; y++){
p[y] = c;
c *= 2;
}
while(low <= top){
int mid = (low + top)/2;
bool gg = true;
for(int i = 1; i <= n; i++){
for(int y = 0; y < sv[i].size(); y++){
if(sv[i][y] > mid * p[min(30LL, v[i])]){
gg = false;
}
}
}
if(gg){
ans = mid;
top = mid-1;
}else{
low = mid+1;
}
}
int j = ans;
if(j == 0){
cout << j << "\n";
return 0;
}
string ns = "";
while(j > 0){
if(j%2 == 1){
ns += '1';
}else{
ns += '0';
}
j/=2;
}
reverse(ns.begin(), ns.end());
j = v[1]+1;
while(j--){
ns += '0';
}
cout << ns << "\n";
return 0;
}
Compilation message (stderr)
poklon.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
24 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |