oj.uz

Submission #634617

# Submission time Handle Problem Language Result Execution time Memory
634617 2022-08-24T15:53:20 Z inksamurai Poklon (COCI17_poklon7) C++17
0 / 120
 561 ms 204816 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";
	}
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:47:7: warning: variable 'compare' set but not used [-Wunused-but-set-variable]
   47 |  auto compare=[&](pii l,pii r)->bool{
      |       ^~~~~~~
poklon.cpp: In instantiation of 'main()::<lambda(auto:23, ll)> [with auto:23 = main()::<lambda(auto:23, ll)>; ll = long long int]':
poklon.cpp:91:11:   required from here
poklon.cpp:84:7: warning: unused variable 'ur' [-Wunused-variable]
   84 |   int ur=cntr[adj[v][1]<=0?v:adj[v][1]-1];
      |       ^~

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 1 ms 212 KB Output isn't correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Incorrect 0 ms 212 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 5 ms 1620 KB Output isn't correct
12 Incorrect 9 ms 1620 KB Output isn't correct
13 Incorrect 25 ms 7316 KB Output isn't correct
14 Incorrect 49 ms 14540 KB Output isn't correct
15 Incorrect 61 ms 8144 KB Output isn't correct
16 Incorrect 172 ms 42360 KB Output isn't correct
17 Incorrect 398 ms 94380 KB Output isn't correct
18 Incorrect 422 ms 100388 KB Output isn't correct
19 Incorrect 502 ms 100780 KB Output isn't correct
20 Incorrect 561 ms 204816 KB Output isn't correct