Submission #634455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634455	2022-08-24T12:48:01 Z	inksamurai	Poklon (COCI17_poklon7)	C++17	6 / 120	1000 ms	262144 KB

poklon

#include <bits/stdc++.h>
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="";
		per(i,sz(a)){
			int v=a[i]-'0',u=b[i]-'0';
			v-=u;
			v-=car;
			if(v<0){
				v=1;
				car=1;
			}else{
				car=0;
			}
			tmp.pb((char)(v+'0'));
		}
		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);
		}
		// if(v==1) print(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)){
			rep(_,max(sl.fi,sr.fi)-cnt){
				sl.se+="0";
			}
		}
		sl.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

6.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Incorrect	1 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	1 ms	212 KB	Output isn't correct
8	Incorrect	1 ms	320 KB	Output isn't correct
9	Incorrect	7 ms	468 KB	Output isn't correct
10	Incorrect	2 ms	328 KB	Output isn't correct
11	Execution timed out	1092 ms	3344 KB	Time limit exceeded
12	Execution timed out	1070 ms	2960 KB	Time limit exceeded
13	Execution timed out	1093 ms	14276 KB	Time limit exceeded
14	Execution timed out	1086 ms	28692 KB	Time limit exceeded
15	Incorrect	100 ms	7488 KB	Output isn't correct
16	Execution timed out	1092 ms	75124 KB	Time limit exceeded
17	Execution timed out	1082 ms	161204 KB	Time limit exceeded
18	Execution timed out	1079 ms	178876 KB	Time limit exceeded
19	Execution timed out	1088 ms	144892 KB	Time limit exceeded
20	Runtime error	336 ms	262144 KB	Execution killed with signal 9