Submission #634469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634469	2022-08-24T13:06:00 Z	inksamurai	Poklon (COCI17_poklon7)	C++17	66 / 120	1000 ms	262144 KB

poklon

#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

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 s="";
		while(v){
			s+=(char)(v%2+'0');
			v/=2;
		}
		reverse(s.begin(), s.end());
		return s;
	};
	auto sub=[&](string a,string b){
		int car=0;
		string tmp="";
		int j=sz(b)-1;
		per(i,sz(a)){
			int v=a[i]-'0';
			int u=(j<0?0:b[j]-'0');
			v-=u;
			v-=car;
			if(v<0){
				v=1;
				car=1;
			}else{
				car=0;
			}
			tmp.pb((char)(v+'0'));
			j-=1;
		}
		while(sz(tmp) and tmp.back()=='0'){
			tmp.pop_back();
		}
		reverse(tmp.begin(), tmp.end());
		return tmp;
	};
	auto dfs=[&](auto&self,int v)->pair<int,string>{
		pair<int,string> sl,sr;
		rep(i,sz(adj[v])){
			int u=adj[v][i];
			if(i==0){
				if(u>0){
					sl=self(self,u-1);
				}else{
					sl={0,bintostr(-u)};
				}
			}else{
				if(u>0){
					sr=self(self,u-1);
				}else{
					sr={0,bintostr(-u)};
				}
			}
		}
		if(sz(sl.se)<sz(sr.se) or (sz(sl.se)==sz(sr.se) and sl.se<sr.se)){
			swap(sl,sr);
		}
		// print(v,sl.se,sr.se);
		string tmp=sub(sl.se,sr.se);
		int cnt=0;
		per(i,sz(tmp)){
			if(tmp[i]=='1'){
				break;
			}
			cnt+=1;
		}
		if(cnt!=sz(tmp) and sr.fi>cnt){
			rep(_,max(sl.fi,sr.fi)){
				sl.se+="0";
			}
		}
		sl.fi=max(sl.fi,sr.fi)+1;
		sl.se+="0";
		// if(v==1) print(sl.se);
		return sl;
	};
	pair<int,string> res=dfs(dfs,0);
	print(res.se);
}

Subtask #1

66.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Incorrect	0 ms	212 KB	Output isn't correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	90 ms	2772 KB	Output is correct
12	Correct	56 ms	2388 KB	Output is correct
13	Execution timed out	1097 ms	12888 KB	Time limit exceeded
14	Execution timed out	1085 ms	26572 KB	Time limit exceeded
15	Incorrect	99 ms	5816 KB	Output isn't correct
16	Execution timed out	1096 ms	69048 KB	Time limit exceeded
17	Execution timed out	1106 ms	146464 KB	Time limit exceeded
18	Execution timed out	1097 ms	164240 KB	Time limit exceeded
19	Execution timed out	1094 ms	126232 KB	Time limit exceeded
20	Runtime error	345 ms	262144 KB	Execution killed with signal 9