oj.uz

Submission #98793

# Submission time Handle Problem Language Result Execution time Memory
98793 2019-02-25T23:52:53 Z thiago4532 Poklon (COCI17_poklon7) C++17
48 / 120
 426 ms 117852 KB 
#include <bits/stdc++.h>
#define left _left
#define right _right
#define int int64_t

using namespace std;
typedef int 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 28 ms 23800 KB Output is correct
2 Correct 29 ms 23800 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 26 ms 23808 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 30 ms 23928 KB Output is correct
7 Correct 25 ms 23948 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Incorrect 23 ms 23936 KB Output isn't correct
10 Incorrect 23 ms 23908 KB Output isn't correct
11 Incorrect 31 ms 24568 KB Output isn't correct
12 Incorrect 29 ms 24704 KB Output isn't correct
13 Incorrect 43 ms 27376 KB Output isn't correct
14 Incorrect 59 ms 30828 KB Output isn't correct
15 Incorrect 58 ms 29548 KB Output isn't correct
16 Incorrect 157 ms 46292 KB Output isn't correct
17 Incorrect 329 ms 75456 KB Output isn't correct
18 Incorrect 380 ms 77120 KB Output isn't correct
19 Incorrect 426 ms 85828 KB Output isn't correct
20 Incorrect 425 ms 117852 KB Output isn't correct