Submission #634474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634474	2022-08-24T13:10:18 Z	inksamurai	Poklon (COCI17_poklon7)	C++17	114 / 120	572 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="";
		if(v==0) return s="0";
		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);
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:42:7: warning: variable 'sub' set but not used [-Wunused-but-set-variable]
   42 |  auto sub=[&](string a,string b){
      |       ^~~

Subtask #1

114.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	Correct	1 ms	212 KB	Output is correct
6	Correct	0 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	1 ms	340 KB	Output is correct
11	Correct	6 ms	2388 KB	Output is correct
12	Correct	7 ms	2132 KB	Output is correct
13	Correct	31 ms	11408 KB	Output is correct
14	Correct	60 ms	23272 KB	Output is correct
15	Correct	52 ms	5708 KB	Output is correct
16	Correct	197 ms	61088 KB	Output is correct
17	Correct	461 ms	130636 KB	Output is correct
18	Correct	478 ms	145880 KB	Output is correct
19	Correct	572 ms	115268 KB	Output is correct
20	Runtime error	359 ms	262144 KB	Execution killed with signal 9