oj.uz

답안 #634474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634474 2022-08-24T13:10:18 Z inksamurai Poklon (COCI17_poklon7) C++17
114 / 120
 572 ms 262144 KB 
#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

# 결과 실행 시간 메모리 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