Submission #45044

#	Time	Username	Problem	Language	Result	Execution time	Memory
45044		Xellos	Poklon (COCI17_poklon7)	C++14	120 / 120	821 ms	262144 KiB

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 / 120