oj.uz

Submission #387932

# Submission time Handle Problem Language Result Execution time Memory
387932 2021-04-09T14:22:18 Z rama_pang Synchronization (JOI13_synchronization) C++17
100 / 100
 208 ms 11200 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> que = {1};
  vector<int> depth(N + 1);
  depth[1] = 1;
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (auto v : adj[u]) if (!depth[v]) {
      depth[v] = depth[u] + 1;
      que.emplace_back(v);
    }
  }

  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:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |     scanf("%d", &e);
      |     ~~~~~^~~~~~~~~~
synchronization.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |     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 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 12 ms 1352 KB Output is correct
8 Correct 10 ms 1284 KB Output is correct
9 Correct 10 ms 1280 KB Output is correct
10 Correct 141 ms 10300 KB Output is correct
11 Correct 122 ms 10344 KB Output is correct
12 Correct 96 ms 10176 KB Output is correct
13 Correct 93 ms 10632 KB Output is correct
14 Correct 119 ms 10300 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10364 KB Output is correct
2 Correct 76 ms 10228 KB Output is correct
3 Correct 65 ms 10196 KB Output is correct
4 Correct 63 ms 10132 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 0 ms 216 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 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 12 ms 1344 KB Output is correct
8 Correct 129 ms 10360 KB Output is correct
9 Correct 125 ms 10416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 10484 KB Output is correct
2 Correct 97 ms 10628 KB Output is correct
3 Correct 113 ms 10748 KB Output is correct
4 Correct 119 ms 10748 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 0 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 1356 KB Output is correct
7 Correct 159 ms 10512 KB Output is correct
8 Correct 138 ms 10364 KB Output is correct
9 Correct 133 ms 11200 KB Output is correct
10 Correct 208 ms 10988 KB Output is correct
11 Correct 111 ms 11020 KB Output is correct
12 Correct 109 ms 10976 KB Output is correct
13 Correct 99 ms 10896 KB Output is correct