oj.uz

Submission #577727

# Submission time Handle Problem Language Result Execution time Memory
577727 2022-06-15T08:26:06 Z mosiashvililuka Poklon (COCI17_poklon7) C++14
114 / 120
 402 ms 118680 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=4000009;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,cnt,lf[N],rg[N],f[N],dp[N],jm[N],msh[N],pas,p[N],pi;
void dfs(long long q, long long w){
	msh[q]=w;
	if(q>a){
		dp[q]=1;
		return;
	}
	dfs(lf[q],q);dfs(rg[q],q);
	int qw=max(dp[lf[q]],dp[rg[q]]);
	jm[lf[q]]=qw-dp[lf[q]];
	jm[rg[q]]=qw-dp[rg[q]];
	dp[q]=qw+1;
}
void dfs2(long long q){
	jm[q]+=jm[msh[q]];
	if(q>a) return;
	dfs2(lf[q]);dfs2(rg[q]);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;cnt=a;
	for(i=1; i<=a; i++){
		cin>>c>>d;
		if(c>0){
			lf[i]=c;
		}else{
			cnt++;f[cnt]=-c;
			lf[i]=cnt;
		}
		if(d>0){
			rg[i]=d;
		}else{
			cnt++;f[cnt]=-d;
			rg[i]=cnt;
		}
	}
	dfs(1,0);dfs2(1);
	for(i=a+1; i<=cnt; i++){
		zx=1;xc=0;jm[i]+=dp[i]-1;
		//cout<<f[i]<<" "<<jm[i]<<"\n";
		while(zx<f[i]){
			zx*=2;xc++;
		}
		if(xc<=jm[i]){
			c=1;
		}else{
			d=(1LL<<jm[i]);
			c=f[i]/d;
			if(f[i]%d!=0) c++;
		}
		pas=max(pas,c);
	}
	//cout<<pas<<"\n";
	pi=0;c=pas;
	while(c>0){
		pi++;p[pi]=c%2;
		c/=2;
	}
	//cout<<dp[1]<<"\n";
	for(i=pi; i>=1; i--){
		cout<<p[i];
	}
	for(i=1; i<=dp[1]-1; i++){
		cout<<0;
	}
	return 0;
}

Subtask #1
114.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 16 ms 5060 KB Output is correct
14 Correct 32 ms 9728 KB Output is correct
15 Correct 27 ms 7376 KB Output is correct
16 Correct 110 ms 30124 KB Output is correct
17 Correct 304 ms 68464 KB Output is correct
18 Correct 247 ms 71076 KB Output is correct
19 Correct 402 ms 79296 KB Output is correct
20 Correct 344 ms 118680 KB Output is correct