Submission #634642

#	Time	Username	Problem	Language	Result	Execution time	Memory
634642		inksamurai	Poklon (COCI17_poklon7)	C++17	120 / 120	681 ms	177380 KiB

poklon

#include <bits/stdc++.h>
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;

vi adj[_n];
int cntr[_n];
pii rbe[_n];

string bintostr(int v){
	if(v==0) return "0";
	string s="";
	while(v>0){
		s+=(char)((v%2)+'0');
		v/=2;
	}
	reverse(s.begin(), s.end());
	return s;
}

bool compare(pii l,pii r){
	if(l.se!=r.se){
		return l.se>r.se;
	}
	string sl=bintostr(l.fi);
	string sr=bintostr(r.fi);
	return sl>sr;
}

void dfs(int v){
	int ma=-1;
	rep(i,sz(adj[v])){
		int u=adj[v][i];
		if(i==0){
			if(u>0){
				dfs(u-1);
			}else{
				ma=max(ma,-u);
			}
		}else{
			if(u>0){
				dfs(u-1);
			}else{
				ma=max(ma,-u);
			}
		}
	}
	cntr[v]=v;
	if(ma>=0){
		rbe[v]={ma,sz(bintostr(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];
	cntr[v]=ul;
	if(compare(rbe[ur],rbe[ul])){
		cntr[v]=ur;
	}
	rbe[cntr[v]].se+=1;
}


signed main(){
_3PGDklf;
	int n;
	cin>>n;
	rep(i,n){
		int ul,ur;
		cin>>ul>>ur;
		adj[i].pb(ul);
		adj[i].pb(ur);
	}
	dfs(0);
	pii p=rbe[cntr[0]];
	string tmp=bintostr(p.fi);
	cout<<tmp;
	rep(_,p.se-sz(tmp)){
		cout<<"0";
	}
}

• Subtask 1: 120 / 120