Submission #634635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634635	2022-08-24T16:14:05 Z	inksamurai	Poklon (COCI17_poklon7)	C++17	120 / 120	338 ms	157868 KB

poklon

#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=1000001;

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(29ll,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";
	}
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	3 ms	1364 KB	Output is correct
12	Correct	4 ms	1492 KB	Output is correct
13	Correct	17 ms	6172 KB	Output is correct
14	Correct	40 ms	12132 KB	Output is correct
15	Correct	32 ms	8116 KB	Output is correct
16	Correct	111 ms	36624 KB	Output is correct
17	Correct	260 ms	82540 KB	Output is correct
18	Correct	264 ms	86692 KB	Output is correct
19	Correct	337 ms	92468 KB	Output is correct
20	Correct	338 ms	157868 KB	Output is correct