oj.uz

Submission #98789

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

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]);
}

int 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 2 ms 428 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 368 KB Output isn't correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Incorrect 3 ms 380 KB Output isn't correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Incorrect 3 ms 420 KB Output isn't correct
10 Incorrect 4 ms 384 KB Output isn't correct
11 Incorrect 16 ms 892 KB Output isn't correct
12 Incorrect 13 ms 1024 KB Output isn't correct
13 Incorrect 69 ms 2800 KB Output isn't correct
14 Incorrect 131 ms 4948 KB Output isn't correct
15 Incorrect 98 ms 4612 KB Output isn't correct
16 Incorrect 396 ms 15696 KB Output isn't correct
17 Incorrect 939 ms 35192 KB Output isn't correct
18 Execution timed out 1041 ms 36108 KB Time limit exceeded
19 Execution timed out 1004 ms 23952 KB Time limit exceeded
20 Execution timed out 1057 ms 25292 KB Time limit exceeded