Submission #43550

#	Time	Username	Problem	Language	Result	Execution time	Memory
43550		KieranHorgan	Poklon (COCI17_poklon7)	C++14	36 / 120	1082 ms	127036 KiB

poklon

#pragma GCC optimize("03")
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
int adj[400005][2];
int weight[4000005];
int scales[400005];

void solve(int idx) {
  int l = adj[idx][0];
  int r = adj[idx][1];
  if(l && r) {
    solve(l);
    solve(r);

    weight[idx] += weight[l];
    weight[idx] += weight[r];
    int lcm = max(scales[l], scales[r]);
    while(weight[l] != weight[r]) {
      if(weight[l] < weight[r]) {
        int div = ceil((double)(weight[r]-weight[l])/scales[l]);
        weight[l] += scales[l]*div;
        weight[idx] += scales[l]*div;
      } else {
        int div = ceil((double)(weight[l]-weight[r])/scales[r]);
        weight[r] += scales[r]*div;
        weight[idx] += scales[r]*div;
      }
    }
    scales[idx] = 2*lcm;
  }
}

int nextIdx;

signed main() {
  cin >> n;
  nextIdx = n+1;
  for(int i = 1; i <= n; i++) {
    int l, r;
    cin >> l >> r;
    if(l > 0) adj[i][0] = l;
    else {
      weight[nextIdx] += abs(l);
      scales[nextIdx] = 1;
      adj[i][0] = nextIdx++;
    }
    if(r > 0) adj[i][1] = r;
    else {
      weight[nextIdx] += abs(r);
      scales[nextIdx] = 1;
      adj[i][1] = nextIdx++;
    }
  }

  solve(1);
  int res = weight[1];
  string ans;
  while(res) {
    if(res%2) ans += '1';
    else      ans += '0';
    res/=2;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}

• Subtask 1: 36 / 120