Submission #577695

#	Time	Username	Problem	Language	Result	Execution time	Memory
577695		GioChkhaidze	Poklon (COCI17_poklon7)	C++14	120 / 120	288 ms	122724 KiB

poklon

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int N = 3e6 + 6;

int n, lf[N], rf[N], c[N];

pair < int , pair < int , int > > dfs(int x) {
	if (x > n) {
		int sz = (int)log2(c[x]) + 1;
		return {c[x], {sz, sz}};
	}
	pair < int ,  pair < int , int > > Lf = dfs(lf[x]);
	pair < int ,  pair < int , int > > Rf = dfs(rf[x]);
	++Lf.s.f, ++Rf.s.f;
	if (Lf.s.f > Rf.s.f) return Lf;
	if (Lf.s.f < Rf.s.f) return Rf;
	if (Lf.s.s < Rf.s.s) {
		if (Lf.f * (1 << (Rf.s.s - Lf.s.s)) > Rf.f) 
			return Lf;
		return Rf;
	}
	if (Lf.s.s > Rf.s.s) {
		if (Rf.f * (1 << (Lf.s.s - Rf.s.s)) > Lf.f) 
			return Rf;
		return Lf;
	}
	if (Lf.f > Rf.f) return Lf;
	return Rf;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	int ts = n;
	for (int i = 1; i <= n; ++i) {
		cin >> lf[i] >> rf[i];
		if (lf[i] < 0) {
			++ts;
			c[ts] = -lf[i];
			lf[i] = ts;
		}
		if (rf[i] < 0) {
			++ts;
			c[ts] = -rf[i];
			rf[i] = ts;
		}
	}
	pair < int ,  pair < int , int > > ans = dfs(1);
	for (int i = ans.s.s - 1; i >= 0; --i) {
		cout << ((ans.f >> i) & 1);
	}
	for (int i = 0; i < ans.s.f - ans.s.s; ++i) {
		cout << 0;
	} 
}

• Subtask 1: 120 / 120