oj.uz

Submission #43550

# Submission time Handle Problem Language Result Execution time Memory
43550 2018-03-17T18:19:00 Z KieranHorgan Poklon (COCI17_poklon7) C++14
36 / 120
 1000 ms 127036 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Incorrect 2 ms 648 KB Output isn't correct
6 Incorrect 1 ms 648 KB Output isn't correct
7 Correct 1 ms 668 KB Output is correct
8 Correct 2 ms 732 KB Output is correct
9 Execution timed out 1067 ms 732 KB Time limit exceeded
10 Incorrect 2 ms 828 KB Output isn't correct
11 Execution timed out 1070 ms 1664 KB Time limit exceeded
12 Execution timed out 1082 ms 1964 KB Time limit exceeded
13 Execution timed out 1070 ms 6400 KB Time limit exceeded
14 Execution timed out 1073 ms 12348 KB Time limit exceeded
15 Execution timed out 1072 ms 12348 KB Time limit exceeded
16 Runtime error 310 ms 36880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 370 ms 43708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 376 ms 50432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 395 ms 57468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 413 ms 127036 KB Execution killed with signal 11 (could be triggered by violating memory limits)