oj.uz

Submission #98798

# Submission time Handle Problem Language Result Execution time Memory
98798 2019-02-26T00:07:20 Z thiago4532 Poklon (COCI17_poklon7) C++17
48 / 120
 373 ms 74852 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;
	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
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 26 ms 23896 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 25 ms 23908 KB Output is correct
5 Correct 27 ms 23900 KB Output is correct
6 Correct 23 ms 23908 KB Output is correct
7 Correct 25 ms 23800 KB Output is correct
8 Correct 23 ms 23936 KB Output is correct
9 Incorrect 24 ms 23808 KB Output isn't correct
10 Incorrect 26 ms 23992 KB Output isn't correct
11 Incorrect 28 ms 24448 KB Output isn't correct
12 Incorrect 28 ms 24472 KB Output isn't correct
13 Incorrect 51 ms 25972 KB Output isn't correct
14 Incorrect 60 ms 28020 KB Output isn't correct
15 Incorrect 59 ms 27504 KB Output isn't correct
16 Incorrect 209 ms 37088 KB Output isn't correct
17 Incorrect 307 ms 54228 KB Output isn't correct
18 Incorrect 295 ms 54996 KB Output isn't correct
19 Incorrect 373 ms 60628 KB Output isn't correct
20 Incorrect 342 ms 74852 KB Output isn't correct