Submission #577727

#	Time	Username	Problem	Language	Result	Execution time	Memory
577727		mosiashvililuka	Poklon (COCI17_poklon7)	C++14	114 / 120	402 ms	118680 KiB

poklon

#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 / 120