#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3PGDklf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
const int _n=10001;
int cntr[_n];
pii rbe[_n];
signed main(){
_3PGDklf;
int n;
cin>>n;
vec(vi) adj(n);
rep(i,n){
int ul,ur;
cin>>ul>>ur;
adj[i].pb(ul);
adj[i].pb(ur);
}
auto topbit=[&](int n)->int{
per(i,30){
if(n>>i&1){
return i;
}
}
return 1;
};
auto compare=[&](pii l,pii r)->bool{
if(l.se!=r.se){
return l.se>r.se;
}
int m=min(10ll,max(l.se,r.se));
int u=l.fi,v=r.fi;
int i=topbit(u),j=topbit(v);
u*=(1ll<<(m-i));
v*=(1ll<<(m-j));
// print(u,v,m,i,j);
return u>v;
};
// print(compare(pii(4,3),pii(10,3)));
auto dfs=[&](auto self,int v)->void{
int ma=-1;
rep(i,sz(adj[v])){
int u=adj[v][i];
if(i==0){
if(u>0){
self(self,u-1);
}else{
ma=max(ma,-u);
}
}else{
if(u>0){
self(self,u-1);
}else{
ma=max(ma,-u);
}
}
}
cntr[v]=v;
if(ma>=0){
rbe[v]={ma,topbit(ma)};
}
int ul=cntr[adj[v][0]<=0?v:adj[v][0]-1];
int ur=cntr[adj[v][1]<=0?v:adj[v][1]-1];
// if(v==0) print(ul,rbe[ul].se);
cntr[v]=ul;
if(compare(rbe[ur],rbe[ul])){
// print(v);
cntr[v]=ur;
}
// if(v==0) print(rbe[cntr[ul]].fi,rbe[cntr[ur]].fi);
// print(v,rbe[cntr[v]].fi);
if(rbe[cntr[v]].fi!=0){
rbe[cntr[v]].se+=1;
}
};
dfs(dfs,0);
pii p=rbe[cntr[0]];
int v=p.fi;
// print(v);
string s="";
while(v){
s+=(char)((v%2)+'0');
v/=2;
}
reverse(s.begin(), s.end());
cout<<s;
rep(_,p.se+1-sz(s)){
cout<<"0";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 12 |
Runtime error |
5 ms |
2772 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
17 ms |
7380 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
32 ms |
12876 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
31 ms |
11700 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
114 ms |
39120 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
254 ms |
89676 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
242 ms |
90572 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
303 ms |
112460 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
423 ms |
262144 KB |
Execution killed with signal 11 |
