Submission #98790

#	Time	Username	Problem	Language	Result	Execution time	Memory
98790		thiago4532	Poklon (COCI17_poklon7)	C++17	0 / 120	1074 ms	79096 KiB

poklon

#include <bits/stdc++.h>
#define left _left
#define right _right
#define int uint_fast64_t

using namespace std;
const int maxn = 1e6 + 10;
int left[maxn], right[maxn];
int val[maxn], nivel[maxn];
int n;

void dfs(int u){
	if(left[u] > 0) nivel[left[u]] = nivel[u] + 1, dfs(left[u]);
	if(right[u] > 0) nivel[right[u]] = nivel[u] + 1, dfs(right[u]);
}

int32_t main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		int a, b;
		cin >> a >> b;
		left[i] = a;
		right[i] = b;
	}
	nivel[1] = 1;
	dfs(1);
	vector< pair<int, int> > v;
	for(int i=1;i<=n;i++)
		v.push_back({nivel[i], i});

	sort(v.begin(), v.end(), greater< pair<int, int> >());
	for(int i=0;i<(int)v.size();i++){
		int u = v[i].second;

		if(left[u] > 0 && right[u] > 0){
			val[left[u]] = max(val[left[u]], val[right[u]]);
			val[right[u]] = max(val[left[u]], val[right[u]]);

			val[u] = val[left[u]] + val[right[u]];
		}else if(left[u] > 0 || right[u] > 0){
			if(left[u] < 0) swap(left[u], right[u]);
			
			if(-right[u] <= val[left[u]]) right[u] = -val[left[u]];
			else{
				val[left[u]] = -right[u];
				if(val[left[u]] % 2 != 0) val[left[u]]++, right[u]--;
			}
			val[u] = val[left[u]] - right[u];
		}else{
			left[u] = min(left[u], right[u]);
			right[u] = min(left[u], right[u]);

			val[u] = -(left[u] + right[u]);
		}
	}

	cout << val[1] << "\n";
	return 0;
}

• Subtask 1: 0 / 120