Submission #387929

#TimeUsernameProblemLanguageResultExecution timeMemory
387929rama_pangSynchronization (JOI13_synchronization)C++17
100 / 100
140 ms13160 KiB
#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 (stderr)

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 {
      |              ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...