oj.uz

Submission #98795

# Submission time Handle Problem Language Result Execution time Memory
98795 2019-02-25T23:55:48 Z thiago4532 Poklon (COCI17_poklon7) C++17
48 / 120
 427 ms 75036 KB 
#include <bits/stdc++.h>
#define left _left
#define right _right

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;
ll left[maxn], right[maxn];
ll val[maxn];
int nivel[maxn];
int n;
vector<int> teste[maxn];

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(){
	ios::sync_with_stdio(false), cin.tie(0);
	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());
	reverse(v.begin(), v.end());

	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]);
		}
	}
	
	string str;
	if(!val[1]) str = "0";
	
	while(val[1]){
		str += '0' + (val[1]%2);
		val[1] /= 2;
	}
	reverse(str.begin(), str.end());
	cout << str << "\n";
	return 0;
}

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 30 ms 23936 KB Output is correct
3 Correct 27 ms 24056 KB Output is correct
4 Correct 27 ms 23936 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 20 ms 23808 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 28 ms 23928 KB Output is correct
9 Incorrect 25 ms 23808 KB Output isn't correct
10 Incorrect 22 ms 23936 KB Output isn't correct
11 Incorrect 34 ms 24448 KB Output isn't correct
12 Incorrect 30 ms 24448 KB Output isn't correct
13 Incorrect 42 ms 26020 KB Output isn't correct
14 Incorrect 56 ms 28016 KB Output isn't correct
15 Incorrect 59 ms 27632 KB Output isn't correct
16 Incorrect 134 ms 36968 KB Output isn't correct
17 Incorrect 360 ms 54204 KB Output isn't correct
18 Incorrect 347 ms 54940 KB Output isn't correct
19 Incorrect 427 ms 60984 KB Output isn't correct
20 Incorrect 355 ms 75036 KB Output isn't correct