oj.uz

Submission #98796

# Submission time Handle Problem Language Result Execution time Memory
98796 2019-02-26T00:05:40 Z thiago4532 Poklon (COCI17_poklon7) C++17
12 / 120
 379 ms 74836 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]] = min(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;
	if(!val[1]) str = "0";
	
	while(val[1]){
		str += '0' + (val[1]%2);
		val[1] /= 2;
	}
	reverse(str.begin(), str.end());
	cout << str << "\n";
	return 0;
}

Subtask #1
12.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23936 KB Output is correct
2 Correct 25 ms 23936 KB Output is correct
3 Incorrect 23 ms 23928 KB Output isn't correct
4 Incorrect 24 ms 23808 KB Output isn't correct
5 Incorrect 30 ms 23932 KB Output isn't correct
6 Incorrect 30 ms 23928 KB Output isn't correct
7 Incorrect 22 ms 23800 KB Output isn't correct
8 Incorrect 24 ms 23936 KB Output isn't correct
9 Incorrect 26 ms 23928 KB Output isn't correct
10 Incorrect 23 ms 23936 KB Output isn't correct
11 Incorrect 28 ms 24484 KB Output isn't correct
12 Incorrect 29 ms 24448 KB Output isn't correct
13 Incorrect 48 ms 25960 KB Output isn't correct
14 Incorrect 63 ms 28016 KB Output isn't correct
15 Incorrect 76 ms 27504 KB Output isn't correct
16 Incorrect 145 ms 36964 KB Output isn't correct
17 Incorrect 302 ms 54260 KB Output isn't correct
18 Incorrect 325 ms 54996 KB Output isn't correct
19 Incorrect 379 ms 60760 KB Output isn't correct
20 Incorrect 338 ms 74836 KB Output isn't correct