oj.uz

Submission #634642

# Submission time Handle Problem Language Result Execution time Memory
634642 2022-08-24T16:17:43 Z inksamurai Poklon (COCI17_poklon7) C++17
120 / 120
 681 ms 177380 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23780 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23760 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 16 ms 23840 KB Output is correct
11 Correct 18 ms 24760 KB Output is correct
12 Correct 19 ms 24660 KB Output is correct
13 Correct 43 ms 28640 KB Output is correct
14 Correct 86 ms 33808 KB Output is correct
15 Correct 107 ms 28108 KB Output is correct
16 Correct 225 ms 52012 KB Output is correct
17 Correct 508 ms 86232 KB Output is correct
18 Correct 509 ms 91340 KB Output is correct
19 Correct 664 ms 86304 KB Output is correct
20 Correct 681 ms 177380 KB Output is correct