oj.uz

Submission #387931

# Submission time Handle Problem Language Result Execution time Memory
387931 2021-04-09T14:20:34 Z rama_pang Synchronization (JOI13_synchronization) C++17
100 / 100
 172 ms 18116 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;
  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

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.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 0 ms 204 KB Output is correct
4 Correct 0 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 9 ms 1228 KB Output is correct
8 Correct 10 ms 1284 KB Output is correct
9 Correct 10 ms 1228 KB Output is correct
10 Correct 116 ms 9796 KB Output is correct
11 Correct 131 ms 9824 KB Output is correct
12 Correct 113 ms 17476 KB Output is correct
13 Correct 95 ms 10220 KB Output is correct
14 Correct 113 ms 9796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 13832 KB Output is correct
2 Correct 82 ms 13780 KB Output is correct
3 Correct 66 ms 17532 KB Output is correct
4 Correct 68 ms 17436 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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 12 ms 1996 KB Output is correct
8 Correct 131 ms 17832 KB Output is correct
9 Correct 127 ms 17668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 17732 KB Output is correct
2 Correct 98 ms 17940 KB Output is correct
3 Correct 99 ms 18084 KB Output is correct
4 Correct 101 ms 18116 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 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 13 ms 1228 KB Output is correct
7 Correct 162 ms 10096 KB Output is correct
8 Correct 130 ms 17660 KB Output is correct
9 Correct 121 ms 10556 KB Output is correct
10 Correct 172 ms 10524 KB Output is correct
11 Correct 110 ms 14336 KB Output is correct
12 Correct 112 ms 14412 KB Output is correct
13 Correct 99 ms 18048 KB Output is correct