oj.uz

Submission #98794

# Submission time Handle Problem Language Result Execution time Memory
98794 2019-02-25T23:54:14 Z thiago4532 Poklon (COCI17_poklon7) C++17
48 / 120
 405 ms 74840 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;
	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 24 ms 23928 KB Output is correct
2 Correct 24 ms 23936 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 27 ms 23928 KB Output is correct
6 Correct 23 ms 23808 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Incorrect 28 ms 23928 KB Output isn't correct
10 Incorrect 28 ms 23936 KB Output isn't correct
11 Incorrect 26 ms 24448 KB Output isn't correct
12 Incorrect 32 ms 24440 KB Output isn't correct
13 Incorrect 53 ms 25972 KB Output isn't correct
14 Incorrect 56 ms 28144 KB Output isn't correct
15 Incorrect 56 ms 27504 KB Output isn't correct
16 Incorrect 138 ms 37032 KB Output isn't correct
17 Incorrect 340 ms 54356 KB Output isn't correct
18 Incorrect 363 ms 54868 KB Output isn't correct
19 Incorrect 405 ms 60764 KB Output isn't correct
20 Incorrect 404 ms 74840 KB Output isn't correct