Submission #1239569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239569		Amaarsaa	Poklon (COCI17_poklon7)	C++20	120 / 120	873 ms	49432 KiB

poklon

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 2;


string To_Bin(ll x) {
    ll i, r;
    string str = "";
    for (i = 30; i >= 0; i --) {
        r = 1<<i;
        if ( x >= r) {
            x -= r;
            str = str + "1";
        }
        else str = str + "0";
    }
    r = 0;
    while ( r < str.size() && str[r] == '0') r ++; 
    str = str.substr(r, str.size() - r);
    return str;
}
ll lef[N], rig[N];
ll parent[N], deg[N] = {0}, val[N], teg[N];

void Update(ll par, ll kid) {
	if ( val[par] == 0) {
		val[par] = val[kid];
		teg[par] = teg[kid] + 1;
		return ;
	}
	ll val1, val2, teg1, teg2;
	val1 = val[par];
	val2 = val[kid];
	teg1 = teg[par];
	teg2 = teg[kid] + 1;
	if ( teg1 < teg2) {
		swap(teg1, teg2);
		swap(val1, val2);
	}
	ll dif = teg1 - teg2;
	if ( dif > 30) {
		val[par] = val1;
		teg[par] = teg1;
		return ;
	}
	ll value = val1;
	while ( dif > 0 && value <= val2) {
		value *= 2;
		dif --;
	}
	if ( value > val2) {
		val[par] = val1;
		teg[par] = teg1;
		return ;
	}
	val[par] = val2;
	teg[par] = teg2;
}
int main() {
    ll n, m, r, s, x, i, y;

    cin >> n;

	
    for (i = 1; i <= n; i ++){
        cin >> lef[i] >> rig[i];
        if ( lef[i] > 0) {
        	parent[lef[i]]= i;
        	deg[i]++;
		}
		if ( rig[i] >0) {
			parent[rig[i]] = i;
			deg[i] ++;
		}
    }
    
    queue < ll > q;
    
    for (i = 1; i <= n; i ++) {
    	if (deg[i] == 0) {
    		q.push(i);
    		
		}
		val[i] = max(-lef[i], -rig[i]);
		val[i] =max(val[i], 0ll);
    	teg[i]= 0;
	}
    
    while ( !q.empty()) {
    	x = q.front();
    	q.pop();
    	y = parent[x];
    	Update(y, x);
///    	cout << y << " " << x << " " << val[y] << " " << teg[y] << " " << val[x] << " " << teg[x] << endl; 
    	deg[y] --;
    	if ( deg[y] == 0) {
			q.push(y);
		}
	}
	string str = To_Bin(val[1]);
	cout << str;
	for (i =0 ; i <= teg[1]; i ++) cout << 0;
  //  cout << "HI" <<endl;
}

• Subtask 1: 120 / 120