#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
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 bintostr=[&](int v){
string s="";
while(v){
s+=(char)(v%2+'0');
v/=2;
}
reverse(s.begin(), s.end());
return s;
};
auto sub=[&](string a,string b){
int car=0;
string tmp="";
int j=sz(b)-1;
per(i,sz(a)){
int v=a[i]-'0';
int u=(j<0?0:b[j]-'0');
v-=u;
v-=car;
if(v<0){
v=1;
car=1;
}else{
car=0;
}
tmp.pb((char)(v+'0'));
j-=1;
}
while(sz(tmp) and tmp.back()=='0'){
tmp.pop_back();
}
reverse(tmp.begin(), tmp.end());
return tmp;
};
auto dfs=[&](auto&self,int v)->pair<int,string>{
pair<int,string> sl,sr;
rep(i,sz(adj[v])){
int u=adj[v][i];
if(i==0){
if(u>0){
sl=self(self,u-1);
}else{
sl={0,bintostr(-u)};
}
}else{
if(u>0){
sr=self(self,u-1);
}else{
sr={0,bintostr(-u)};
}
}
}
if(sz(sl.se)<sz(sr.se) or (sz(sl.se)==sz(sr.se) and sl.se<sr.se)){
swap(sl,sr);
}
// if(v==1) print(sl.se,sr.se);
string tmp=sub(sl.se,sr.se);
// if(v==0) print(tmp,sl.se,sr.se);
int cnt=0;
per(i,sz(tmp)){
if(tmp[i]=='1'){
break;
}
cnt+=1;
}
if(cnt!=sz(tmp)){
rep(_,max(sl.fi,sr.fi)-cnt){
sl.se+="0";
}
}
sl.fi=max(sl.fi,sr.fi)+1;
sl.se+="0";
// if(v==1) print(sl.se);
return sl;
};
pair<int,string> res=dfs(dfs,0);
print(res.se);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 9 |
Incorrect |
23 ms |
652 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 11 |
Execution timed out |
1084 ms |
4804 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1087 ms |
4308 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1085 ms |
14960 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1090 ms |
28472 KB |
Time limit exceeded |
| 15 |
Incorrect |
107 ms |
5836 KB |
Output isn't correct |
| 16 |
Execution timed out |
1094 ms |
70984 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1084 ms |
148580 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1095 ms |
166220 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1091 ms |
128652 KB |
Time limit exceeded |
| 20 |
Runtime error |
407 ms |
262144 KB |
Execution killed with signal 9 |
