Submission #1235888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235888		altern23	Poklon (COCI17_poklon7)	C++20	54 / 120	399 ms	173576 KiB

poklon

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll len[MAXN + 5], lf[MAXN + 5], rg[MAXN + 5], val[MAXN + 5];

string conv(ll idx){
	string ans = "";
	for(;idx > 0;){
		ans.push_back((idx % 2) + '0');
		idx /= 2;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

void dfs(ll idx){
	pii kiri, kanan;
	if(lf[idx] > 0){
		dfs(lf[idx]);
		kiri = {val[lf[idx]], len[lf[idx]]};
	}
	else kiri = {abs(lf[idx]), 0};
	if(rg[idx] > 0){
		dfs(rg[idx]);
		kanan = {val[rg[idx]], len[rg[idx]]};
	}
	else kanan = {abs(rg[idx]), 0};

	string L = conv(kiri.fi), R = conv(kanan.fi);
	bool use_L = 0, use_R = 0;
	if(L.size() + kiri.sec > R.size() + kanan.sec) use_L = 1;
	else if(L.size() + kiri.sec < R.size() + kanan.sec) use_R = 1;
	else{
		bool cek = 0;
		for(int i = 0; i < (int)max(R.size(), L.size()); i++){
			if(i >= (int)L.size()) break;
			if(i >= (int)R.size() || L[i] > R[i]){
				cek = 1;
				break;
			}
		}
		use_L = cek, use_R = (!cek);
	}
	
	if(use_L) val[idx] = kiri.fi, len[idx] = kiri.sec;
	if(use_R) val[idx] = kanan.fi, len[idx] = kanan.sec;
	len[idx]++;	
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		for(int i = 1; i <= N; i++){
			cin >> lf[i] >> rg[i];
		}
		
		dfs(1);
		cout << conv(val[1]);
		for(int i = 1; i <= len[1]; i++) cout << 0;
		cout << "\n";
	}	
}

/*

*/

• Subtask 1: 54 / 120