Submission #387931

#	Time	Username	Problem	Language	Result	Execution time	Memory
387931		rama_pang	Synchronization (JOI13_synchronization)	C++17	100 / 100	172 ms	18116 KiB

synchronization

#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;
  scanf("%d %d %d", &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;
    scanf("%d %d", &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);
    }
  };
  Dfs(Dfs, 1, 0);

  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;
    scanf("%d", &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;
    scanf("%d", &u);
    printf("%d\n", ans[lct.Root(u)]);
  }
  return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |   scanf("%d %d %d", &N, &M, &Q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |     scanf("%d", &e);
      |     ~~~~~^~~~~~~~~~
synchronization.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |     scanf("%d", &u);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40