oj.uz

Submission #1067319

# Submission time Handle Problem Language Result Execution time Memory
1067319 2024-08-20T14:40:29 Z lmaobruh Tree Rotations (POI11_rot) C++14
100 / 100
 189 ms 40400 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N = 4e5+5, sizeBit = 2e5+5;

int ft[sizeBit];

int get(int p) {
  int tot = 0;
  for (; p <= N/2; p += p & -p)
    tot += ft[p];
  return tot;
}

void upd(int p, int v) {
  for (; p; p -= p & -p)
    ft[p] += v;
}

int n, a[N], curr = 1, sz[N], big[N];
vector<int> g[N];
ll ans[N], inv;

void read() {
  int x;
  cin >> x;
  if (x) return a[curr] = x, void();
  int tmp = curr;
  g[tmp].pb(++curr); g[curr].pb(tmp);
  read(); // cay con trai
  g[tmp].pb(++curr); g[curr].pb(tmp);
  read(); // cay con phai
}

void dfs_sz(int u, int pre = -1) {
  sz[u] = (a[u] > 0); big[u] = 0;
  for (int v : g[u]) if (v != pre) {
    dfs_sz(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[big[u]]) big[u] = v;
  }
}

void add_inv(int u, int pre) {
  if (a[u]) {
    inv += get(a[u]+1);
    return;
  }
  for (int v : g[u]) if (v != pre)
    add_inv(v, u);
}

void add_bit(int u, int pre) {
  if (a[u]) {
    upd(a[u], 1);
    return;
  }
  for (int v : g[u]) if (v != pre)
    add_bit(v, u);
}

void del(int u, int pre) {
  if (a[u]) {
    upd(a[u], -1);
    return;
  }
  for (int v : g[u]) if (v != pre)
    del(v, u);
}

void add(int u, int pre) {
  add_inv(u, pre);
  add_bit(u, pre);
}

void dfs(int u, int pre) {
  if (a[u]) {
    add(u, pre);
    return;
  }
  int node;
  for (int v : g[u]) if (v != pre && v != big[u]) {
    dfs(v, u);
    ans[u] += ans[v];
    del(v, u);
    node = v;
  }
  dfs(big[u], u);
  ans[u] += ans[big[u]];
  inv = 0; add(node, u);
  ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n; read();
  dfs_sz(1, 1); dfs(1, 1);
  cout << ans[1];
}

Compilation message

rot.cpp: In function 'void dfs(int, int)':
rot.cpp:92:48: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |   ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv);
      |                                         ~~~~~~~^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14784 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 3 ms 15452 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Correct 10 ms 15704 KB Output is correct
3 Correct 27 ms 17244 KB Output is correct
4 Correct 8 ms 16320 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18780 KB Output is correct
2 Correct 27 ms 20056 KB Output is correct
3 Correct 28 ms 21596 KB Output is correct
4 Correct 34 ms 21844 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27216 KB Output is correct
2 Correct 38 ms 24916 KB Output is correct
3 Correct 45 ms 23124 KB Output is correct
4 Correct 36 ms 22100 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24916 KB Output is correct
2 Correct 51 ms 26960 KB Output is correct
3 Correct 54 ms 29908 KB Output is correct
4 Correct 52 ms 29780 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31932 KB Output is correct
2 Correct 109 ms 31824 KB Output is correct
3 Correct 89 ms 32080 KB Output is correct
4 Correct 99 ms 31348 KB Output is correct
5 Correct 154 ms 30320 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 31056 KB Output is correct
2 Correct 104 ms 38484 KB Output is correct
3 Correct 109 ms 36568 KB Output is correct
4 Correct 84 ms 39504 KB Output is correct
5 Correct 189 ms 32080 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 31824 KB Output is correct
2 Correct 85 ms 34604 KB Output is correct
3 Correct 152 ms 32556 KB Output is correct
4 Correct 111 ms 33364 KB Output is correct
5 Correct 96 ms 40400 KB Output is correct
6 Correct 178 ms 32592 KB Output is correct