Submission #45044

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
45044	2018-04-11T05:07:11 Z	Xellos	Poklon (COCI17_poklon7)	C++14	120 / 120	821 ms	262144 KB

poklon

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

vector<int> Adep,Aval;

void DFS(int R, vector< vector<int> > &son, vector<int> &W, vector<long long> &Ws) {
	if(son[R].empty()) {
		Adep[R] =0;
		Aval[R] =W[R];
		Ws[R] =W[R];
		return;}
	for(int i =0; i < 2; i++) {
		DFS(son[R][i],son,W,Ws);
		Ws[R] +=Ws[i];}
	if(Aval[son[R][0]] == 0) {
		if(Aval[son[R][1]] == 0) Aval[R] =Adep[R] =0;
		else Aval[R] =Aval[son[R][1]], Adep[R] =Adep[son[R][1]]+1;
		return;}
	if(Aval[son[R][1]] == 0) {
		Aval[R] =Aval[son[R][0]], Adep[R] =Adep[son[R][0]]+1;
		return;}
	int x =min(Adep[son[R][0]],Adep[son[R][1]]);
	if(Adep[son[R][0]] > 31+x) {
		Aval[R] =Aval[son[R][0]], Adep[R] =Adep[son[R][0]]+1;
		return;}
	if(Adep[son[R][1]] > 31+x) {
		Aval[R] =Aval[son[R][1]], Adep[R] =Adep[son[R][1]]+1;
		return;}
	long long x1 =(1LL*Aval[son[R][0]])<<(Adep[son[R][0]]-x);
	long long x2 =(1LL*Aval[son[R][1]])<<(Adep[son[R][1]]-x);
	if(x1 > x2) {
		Aval[R] =Aval[son[R][0]], Adep[R] =Adep[son[R][0]]+1;
		return;}
	else {
		Aval[R] =Aval[son[R][1]], Adep[R] =Adep[son[R][1]]+1;
		return;}
	}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector< vector<int> > son(N);
	vector<int> W(N,0);
	int N0 =N;
	for(int i =0; i < N0; i++) {
		int a,b;
		cin >> a >> b;
		if(a <= 0) {
			son.push_back(vector<int>());
			son[i].push_back(N);
			W.push_back(-a);
			N++;}
		else son[i].push_back(a-1);
		if(b <= 0) {
			son.push_back(vector<int>());
			son[i].push_back(N);
			W.push_back(-b);
			N++;}
		else son[i].push_back(b-1);
		}
	vector<long long> Ws(N);
	Adep.resize(N);
	Aval.resize(N);
	DFS(0,son,W,Ws);
	vector<int> v;
	for(int i =0; i < Adep[0]; i++) v.push_back(0);
	while(Aval[0] > 0) {
		v.push_back(Aval[0]%2);
		Aval[0] /=2;}
	vector<int> v2;
	while(Ws[0] > 0) {
		v2.push_back(Ws[0]%2);
		Ws[0] /=2;}
	while(v2.size() > v.size()) v2.push_back(0);
	for(int i =0; i < (int)v2.size(); i++) v[i] -=v2[i];
	for(int i =0; i < (int)v.size(); i++) {
		if(v[i] < 0) {
			v[i+1] -=(-v[i])/2;
			v[i] +=((-v[i])/2)*2;}
		while(v[i] < 0) {
			v[i+1] -=1;
			v[i] +=2;}
		if(v[i] > 1) {
			v[i+1] +=v[i]/2;
			v[i] -=(v[i]/2)*2;}
		}
	while(!v.empty() && v.back() == 0) v.pop_back();
	if(v.empty()) v.push_back(0);
	reverse(begin(v),end(v));
	for(int i =0; i < (int)v.size(); i++) cout << v[i];
	cout << "\n";
	}

// look at my code
// my code is amazing

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	496 KB	Output is correct
3	Correct	2 ms	496 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	2 ms	664 KB	Output is correct
7	Correct	2 ms	664 KB	Output is correct
8	Correct	2 ms	664 KB	Output is correct
9	Correct	2 ms	664 KB	Output is correct
10	Correct	2 ms	784 KB	Output is correct
11	Correct	9 ms	2336 KB	Output is correct
12	Correct	10 ms	2840 KB	Output is correct
13	Correct	34 ms	9608 KB	Output is correct
14	Correct	66 ms	19332 KB	Output is correct
15	Correct	110 ms	19332 KB	Output is correct
16	Correct	257 ms	61324 KB	Output is correct
17	Correct	577 ms	136224 KB	Output is correct
18	Correct	572 ms	158088 KB	Output is correct
19	Correct	686 ms	189020 KB	Output is correct
20	Correct	821 ms	262144 KB	Output is correct