oj.uz

Submission #98792

# Submission time Handle Problem Language Result Execution time Memory
98792 2019-02-25T23:52:16 Z thiago4532 Poklon (COCI17_poklon7) C++17
48 / 120
 469 ms 106060 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});

	for(int i=1;i<=n;i++){
		teste[nivel[i]].push_back(i);
	}
	v.clear();
	for(int i=n;i>=1;i--){
		while(!teste[i].empty()){
			int u = teste[i].back();
			teste[i].pop_back();
			v.push_back({i, u});
		}
	}

	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;
	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 30 ms 23928 KB Output is correct
2 Correct 27 ms 23900 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 26 ms 23928 KB Output is correct
5 Correct 29 ms 23900 KB Output is correct
6 Correct 2 ms 23908 KB Output is correct
7 Correct 29 ms 23808 KB Output is correct
8 Correct 24 ms 23908 KB Output is correct
9 Incorrect 27 ms 23808 KB Output isn't correct
10 Incorrect 24 ms 23928 KB Output isn't correct
11 Incorrect 26 ms 24448 KB Output isn't correct
12 Incorrect 29 ms 24440 KB Output isn't correct
13 Incorrect 42 ms 26612 KB Output isn't correct
14 Incorrect 57 ms 29524 KB Output isn't correct
15 Incorrect 62 ms 27912 KB Output isn't correct
16 Incorrect 169 ms 41156 KB Output isn't correct
17 Incorrect 351 ms 63280 KB Output isn't correct
18 Incorrect 469 ms 65080 KB Output isn't correct
19 Incorrect 359 ms 69076 KB Output isn't correct
20 Incorrect 391 ms 106060 KB Output isn't correct