oj.uz

Submission #387929

# Submission time Handle Problem Language Result Execution time Memory
387929 2021-04-09T14:16:20 Z rama_pang Synchronization (JOI13_synchronization) C++17
100 / 100
 140 ms 13160 KB 
#include <bits/stdc++.h>
using namespace std;

class SplayTree {
 public:
  struct Node {
    int ch[2] = {0, 0}, p = 0;
    int val = 0;
    Node(int v = 0) : val(v) {}
  };

  vector<Node> T;
  SplayTree(int n) : T(n + 1) {}

  void Push(int x) {

  }

  void Pull(int x) {
    Push(T[x].ch[0]), Push(T[x].ch[1]);
  }

  void Set(int p, int d, int u) {
    T[p].ch[d] = u; T[u].p = p; Pull(p);
  }

  int Dir(int x) {
    if (!x || !T[x].p) return -1;
    return T[T[x].p].ch[0] == x ? 0 : T[T[x].p].ch[1] == x ? 1 : -1;
  }

  void Rot(int x) {
    int y = T[x].p, z = T[y].p;
    int 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;
  }

  void Splay(int x) {
    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) Rot(dx == dy ? y : x);
      Rot(x);
    }
  }
};

class LinkCut : public SplayTree {
 public:
  LinkCut(int n) : SplayTree(n) {}

  void Access(int x) {
    for (int u = x, prv = 0; u; u = T[u].p) {
      Splay(u);
      Set(u, 1, prv);
      prv = u;
    }
    Splay(x);
  }

  void Link(int par, int ch) {
    Access(par), Access(ch), Set(par, 1, ch);
  }

  void Cut(int x) {
    Access(x);
    if (T[x].ch[0]) {
      T[T[x].ch[0]].p = 0;
      T[x].ch[0] = 0;
      Pull(x);
    }
  }

  int Root(int x) {
    Access(x);
    while (T[x].ch[0]) x = T[x].ch[0];
    Access(x);
    return T[x].val;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M, Q;
  cin >> N >> M >> Q;

  vector<vector<int>> adj(N + 1);
  vector<pair<int, int>> edge(N);
  for (int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    edge[i] = {x, y};
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
  }

  vector<int> depth(N + 1);
  const auto Dfs = [&](const auto &self, int u, int p) -> void {
    for (auto v : adj[u]) if (v != p) {
      depth[v] = depth[u] + 1;
      self(self, v, u);
    }
  };

  vector<int> ans(N + 1, 1);
  vector<int> last(N, 0);
  vector<int> state(N, 0);

  LinkCut lct(N);
  for (int i = 1; i <= N; i++) {
    lct.T[i].val = i;
  }

  while (M--) {
    int e;
    cin >> e;
    auto [x, y] = edge[e];
    if (depth[x] > depth[y]) swap(x, y);
    state[e] ^= 1;
    if (state[e] == 0) { // delete edge
      int t = ans[lct.Root(x)];
      lct.Cut(y);
      last[e] = ans[lct.Root(x)] = ans[lct.Root(y)] = t;
    } else { // add edge
      ans[lct.Root(x)] = ans[lct.Root(x)] + ans[lct.Root(y)] - last[e];
      lct.Link(x, y);
    }
  }

  while (Q--) {
    int u;
    cin >> u;
    cout << ans[lct.Root(u)] << '\n';
  }
  return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:104:14: warning: variable 'Dfs' set but not used [-Wunused-but-set-variable]
  104 |   const auto Dfs = [&](const auto &self, int u, int p) -> void {
      |              ^~~

Subtask #1
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 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 8 ms 1356 KB Output is correct
8 Correct 11 ms 1356 KB Output is correct
9 Correct 9 ms 1352 KB Output is correct
10 Correct 122 ms 12040 KB Output is correct
11 Correct 106 ms 12100 KB Output is correct
12 Correct 84 ms 11972 KB Output is correct
13 Correct 73 ms 11996 KB Output is correct
14 Correct 96 ms 11460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 11860 KB Output is correct
2 Correct 64 ms 11700 KB Output is correct
3 Correct 53 ms 11332 KB Output is correct
4 Correct 55 ms 11376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 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 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 10 ms 1516 KB Output is correct
8 Correct 118 ms 12784 KB Output is correct
9 Correct 116 ms 12772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 12772 KB Output is correct
2 Correct 80 ms 12488 KB Output is correct
3 Correct 83 ms 12608 KB Output is correct
4 Correct 82 ms 12576 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 1 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 1484 KB Output is correct
7 Correct 133 ms 13000 KB Output is correct
8 Correct 135 ms 12740 KB Output is correct
9 Correct 120 ms 13160 KB Output is correct
10 Correct 140 ms 12836 KB Output is correct
11 Correct 92 ms 13028 KB Output is correct
12 Correct 90 ms 13124 KB Output is correct
13 Correct 82 ms 12528 KB Output is correct