oj.uz

Submission #98791

# Submission time Handle Problem Language Result Execution time Memory
98791 2019-02-25T23:47:59 Z thiago4532 Poklon (COCI17_poklon7) C++17
12 / 120
 1000 ms 263168 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;
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(){
	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]&1);
		val[1] >>= 1;
	}
	reverse(str.begin(), str.end());
	cout << str << "\n";
	return 0;
}

Subtask #1
12.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 28 ms 23936 KB Output is correct
3 Incorrect 24 ms 23800 KB Output isn't correct
4 Incorrect 26 ms 23808 KB Output isn't correct
5 Runtime error 747 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 28 ms 23936 KB Output isn't correct
7 Incorrect 26 ms 23800 KB Output isn't correct
8 Runtime error 666 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Incorrect 23 ms 23936 KB Output isn't correct
10 Runtime error 683 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 701 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Incorrect 37 ms 24312 KB Output isn't correct
13 Runtime error 763 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 750 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 860 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Execution timed out 1028 ms 263168 KB Time limit exceeded
17 Incorrect 745 ms 54012 KB Output isn't correct
18 Execution timed out 1072 ms 55760 KB Time limit exceeded
19 Execution timed out 1000 ms 57644 KB Time limit exceeded
20 Execution timed out 1016 ms 94544 KB Time limit exceeded