oj.uz

Submission #634618

# Submission time Handle Problem Language Result Execution time Memory
634618 2022-08-24T15:53:35 Z inksamurai Poklon (COCI17_poklon7) C++17
0 / 120
 640 ms 262144 KB 
#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 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;
	};
	auto compare=[&](pii l,pii r)->bool{
		if(l.se!=r.se){
			return l.se>r.se;
		}
		string sl=bintostr(l.fi);
		string sr=bintostr(r.fi);
		while(sz(sl)<sz(sr)){
			sl.pb('0');
		}
		while(sz(sr)<sz(sl)){
			sr.pb('0');
		}
		return sl>sr;
	};
	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,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;
	};
	dfs(dfs,0);
	pii p=rbe[cntr[0]];
	string tmp=bintostr(p.fi);
	cout<<tmp<<"\n";
	rep(_,p.se-sz(tmp)){
		cout<<"0";
	}
}

Subtask #1
0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 340 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 0 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 7 ms 2004 KB Output isn't correct
12 Incorrect 9 ms 2004 KB Output isn't correct
13 Incorrect 34 ms 9332 KB Output isn't correct
14 Incorrect 63 ms 18720 KB Output isn't correct
15 Incorrect 77 ms 8140 KB Output isn't correct
16 Incorrect 217 ms 52228 KB Output isn't correct
17 Incorrect 513 ms 114704 KB Output isn't correct
18 Incorrect 509 ms 124220 KB Output isn't correct
19 Incorrect 640 ms 114620 KB Output isn't correct
20 Runtime error 385 ms 262144 KB Execution killed with signal 9