oj.uz

Submission #441119

# Submission time Handle Problem Language Result Execution time Memory
441119 2021-07-04T09:02:12 Z peijar Synchronization (JOI13_synchronization) C++17
100 / 100
 235 ms 11860 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct SplayTree {
  struct Node {
    int ch[2] = {0, 0}, p = 0;
    int self = 0, path = 0;
    int sub = 0, vir = 0;
    bool flip = 0;
  };
  vector<Node> T;

  SplayTree(int n) : T(n + 1) {}

  void push(int x) {
    if (!x || !T[x].flip)
      return;
    int l = T[x].ch[0], r = T[x].ch[1];

    T[l].flip ^= 1, T[r].flip ^= 1;
    swap(T[x].ch[0], T[x].ch[1]);
    T[x].flip = 0;
  }

  void pull(int x) {
    int l = T[x].ch[0], r = T[x].ch[1];
    push(l);
    push(r);
    T[x].path = T[l].path + T[x].self + T[r].path;
    T[x].sub = T[x].vir + T[l].sub + T[r].sub + T[x].self;
  }

  void set(int x, int d, int y) {
    T[x].ch[d] = y, T[y].p = x;
    pull(x);
  }

  void splay(int x) {
    auto dir = [&](int x) {
      int p = T[x].p;
      if (!p)
        return -1;
      return T[p].ch[0] == x ? 0 : T[p].ch[1] == x ? 1 : -1;
    };
    auto rotate = [&](int x) {
      int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
      set(y, dx, T[x].ch[!dx]);
      set(x, !dx, y);
      if (~dy)
        set(z, dy, x);
      T[x].p = z;
    };
    for (push(x); ~dir(x);) {
      int y = T[x].p, z = T[y].p;
      push(z);
      push(y);
      push(x);
      int dx = dir(x), dy = dir(y);
      if (~dy)
        rotate(dx != dy ? x : y);
      rotate(x);
    }
  }
};

struct LinkCut : SplayTree {
  LinkCut(int n) : SplayTree(n) {}

  int access(int x) {
    int u = x, v = 0;
    for (; u; v = u, u = T[u].p) {
      splay(u);
      int &ov = T[u].ch[1];
      T[u].vir += T[ov].sub;
      T[u].vir -= T[v].sub;
      ov = v;
      pull(u);
    }
    splay(x);
    return v;
  }

  void reroot(int x) {
    access(x);
    T[x].flip ^= 1;
    push(x);
  }

  void link(int u, int v) {
    ++u, ++v;
    reroot(u);
    access(v);
    T[v].vir += T[u].sub;
    T[u].p = v;
    pull(v);
  }

  void cut(int u, int v) {
    ++u, ++v;
    reroot(u);
    access(v);
    T[v].ch[0] = T[u].p = 0;
    pull(v);
  }

  int lca(int u, int v) {
    ++u, ++v;
    if (u == v)
      return u;
    access(u);
    int ret = access(v);
    return T[u].p ? ret : 0;
  }

  int subTree(int u,
              int v) // Calculates subtree aggregate for u when rooted at v
  {
    ++u, ++v;
    reroot(v);
    access(u);
    return T[u].vir + T[u].self;
  }

  int path(int u, int v) // puts v at root, and path to u is in left child.
  {
    ++u, ++v;
    reroot(u);
    access(v);
    return T[v].path;
  }

  void update(int u, int v) {
    ++u;
    access(u);
    T[u].self = v;
    pull(u);
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbUpdates, nbRequetes;
  cin >> nbSommets >> nbUpdates >> nbRequetes;
  vector<pair<int, int>> aretes(nbSommets - 1);
  for (auto &[u, v] : aretes) {
    cin >> u >> v;
    --u, --v;
  }

  LinkCut lct(nbSommets);
  for (int i = 0; i < nbSommets; ++i) {
    lct.update(i, 1);
  }
  vector<bool> state(nbSommets - 1);
  vector<int> lstVal(nbSommets - 1);

  for (int i = 0; i < nbUpdates; ++i) {
    /*cout << "AFTER " << i << " UPDATES : " << endl;
    for (int j = 0; j < nbSommets; ++j)
      cout << lct.subTree(j, j) << ' ';
    cout << endl;*/
    int x;
    cin >> x;
    --x;
    auto [u, v] = aretes[x];
    if (!state[x]) {
      lct.link(u, v);
      lct.update(u, lct.T[u + 1].self - lstVal[x]);
    } else {
      int cur = lct.subTree(u, u);
      lstVal[x] = cur;
      lct.cut(u, v);
      int valU = lct.subTree(u, u);
      int valV = lct.subTree(v, v);
      lct.update(u, lct.T[u + 1].self + valV);
      lct.update(v, lct.T[v + 1].self + valU);
    }
    state[x] = !state[x];
  }
  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int u;
    cin >> u;
    --u;
    cout << lct.subTree(u, u) << '\n';
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 16 ms 1356 KB Output is correct
8 Correct 11 ms 1356 KB Output is correct
9 Correct 11 ms 1384 KB Output is correct
10 Correct 179 ms 11092 KB Output is correct
11 Correct 171 ms 11212 KB Output is correct
12 Correct 140 ms 11112 KB Output is correct
13 Correct 128 ms 10820 KB Output is correct
14 Correct 109 ms 10668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9040 KB Output is correct
2 Correct 85 ms 10744 KB Output is correct
3 Correct 63 ms 10580 KB Output is correct
4 Correct 59 ms 10564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 14 ms 1436 KB Output is correct
8 Correct 154 ms 11332 KB Output is correct
9 Correct 192 ms 11344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 9284 KB Output is correct
2 Correct 94 ms 11592 KB Output is correct
3 Correct 95 ms 11716 KB Output is correct
4 Correct 120 ms 11644 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 14 ms 1436 KB Output is correct
7 Correct 198 ms 11472 KB Output is correct
8 Correct 152 ms 11220 KB Output is correct
9 Correct 147 ms 11588 KB Output is correct
10 Correct 235 ms 11860 KB Output is correct
11 Correct 121 ms 11716 KB Output is correct
12 Correct 122 ms 11600 KB Output is correct
13 Correct 91 ms 11608 KB Output is correct