oj.uz

Submission #98790

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

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

int32_t 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 3 ms 384 KB Output isn't correct
2 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 13 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 47 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 91 ms 3684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 89 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 308 ms 11048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 695 ms 25464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 674 ms 25564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Execution timed out 1074 ms 33080 KB Time limit exceeded
20 Runtime error 904 ms 79096 KB Execution killed with signal 11 (could be triggered by violating memory limits)