oj.uz

Submission #634504

# Submission time Handle Problem Language Result Execution time Memory
634504 2022-08-24T13:30:56 Z inksamurai Poklon (COCI17_poklon7) C++17
114 / 120
 590 ms 262144 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;

int cntr[_n];
string 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 bintostr=[&](int v)->string{
		if(v==0) return "0";
		string s="";
		while(v>0){
			s+=(char)((v%2)+'0');
			v/=2;
		}
		reverse(s.begin(), s.end());
		return s;
	};
	string s="";
	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;
		rbe[v]=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(sz(rbe[ul])<sz(rbe[ur]) or (sz(rbe[ul])==sz(rbe[ur]) and rbe[ul]<rbe[ur])){
			cntr[v]=ur;
		}
		rbe[cntr[v]]+="0";
		if(cntr[v]!=v){
			rbe[v].clear();
		}
	};
	dfs(dfs,0);
	print(rbe[cntr[0]]);
}

Subtask #1
114.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 15 ms 31524 KB Output is correct
3 Correct 16 ms 31720 KB Output is correct
4 Correct 15 ms 31572 KB Output is correct
5 Correct 16 ms 31596 KB Output is correct
6 Correct 15 ms 31572 KB Output is correct
7 Correct 15 ms 31540 KB Output is correct
8 Correct 18 ms 31572 KB Output is correct
9 Correct 15 ms 31740 KB Output is correct
10 Correct 16 ms 31708 KB Output is correct
11 Correct 22 ms 33512 KB Output is correct
12 Correct 21 ms 33576 KB Output is correct
13 Correct 45 ms 41676 KB Output is correct
14 Correct 73 ms 52184 KB Output is correct
15 Correct 71 ms 41492 KB Output is correct
16 Correct 201 ms 91032 KB Output is correct
17 Correct 469 ms 163724 KB Output is correct
18 Correct 462 ms 173492 KB Output is correct
19 Correct 590 ms 168388 KB Output is correct
20 Runtime error 336 ms 262144 KB Execution killed with signal 9