oj.uz

Submission #1059547

# Submission time Handle Problem Language Result Execution time Memory
1059547 2024-08-15T05:04:58 Z nima_aryan Synchronization (JOI13_synchronization) C++17
100 / 100
 223 ms 29364 KB 
/**
 *    author:  NimaAryan
 *    created: 2024-03-04 20:34:56
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <typename T>
struct Fenwick {
  int n;
  std::vector<T> a;

  Fenwick(int n_ = 0) {
    init(n_);
  }

  void init(int n_) {
    n = n_;
    a.assign(n, T{});
  }

  void add(int x, const T& v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] = a[i - 1] + v;
    }
  }

  T sum(int x) {
    T ans{};
    for (int i = x; i > 0; i -= i & -i) {
      ans = ans + a[i - 1];
    }
    return ans;
  }

  T range_sum(int l, int r) {
    return sum(r) - sum(l);
  }

  int select(const T& k) {
    int x = 0;
    T cur{};
    for (int i = 1 << std::__lg(n); i; i /= 2) {
      if (x + i <= n && cur + a[x + i - 1] <= k) {
        x += i;
        cur = cur + a[x - 1];
      }
    }
    return x;
  }
};

struct Tree {
  int n;
  int maxup;
  vector<vector<int>> adj;
  vector<int> tin, tout;
  vector<int> dfn;
  vector<int> dep;
  vector<vector<int>> up;

  Tree(int n) : n(n), maxup(__lg(n) + 1) {
    adj.resize(n);
  }

  void add_edge(int x, int y) {
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  void work(int r = 0) {
    tin.resize(n), tout.resize(n);
    dfn.resize(n);
    dep.resize(n);
    up.assign(maxup + 1, vector<int>(n));
    int timer = 0;
    function<void(int, int)> dfs = [&](int x, int p) {
      dfn[x] = tin[x] = timer++;
      up[0][x] = p;
      for (int i = 1; i <= maxup; ++i) {
        up[i][x] = up[i - 1][up[i - 1][x]];
      }
      for (int y : adj[x]) {
        if (y != p) {
          dep[y] = dep[x] + 1;
          dfs(y, x);
        }
      }
      tout[x] = timer;
    };
    dfs(r, r);
  }

  bool anc(int x, int y) {
    return tin[x] <= tin[y] && tout[y] <= tout[x];
  }

  int lca(int x, int y) {
    if (anc(x, y)) {
      return x;
    }
    if (anc(y, x)) {
      return y;
    }
    for (int i = maxup; i >= 0; --i) {
      int nx = up[i][x];
      if (!anc(nx, y)) {
        x = nx;
      }
    }
    return up[0][x];
  }

  int dist(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
  }

  int jump(int x, int k) {
    for (int i = 0; i <= maxup; ++i) {
      if (k >> i & 1) {
        x = up[i][x];
      }
    }
    return x;
  }

  int walk(int x, int y, int k) {
    return k > dep[x] - dep[lca(x, y)] ? jump(y, dist(x, y) - k) : jump(x, k);
  }
};

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

  int n, m, q;
  cin >> n >> m >> q;

  vector<array<int, 2>> e;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    e.push_back({u, v});
  }

  Tree t(n);
  for (auto& [u, v] : e) {
    t.add_edge(u, v);
  }
  t.work();

  for (auto& [u, v] : e) {
    if (t.dep[u] > t.dep[v]) {
      swap(u, v);
    }
  }

  Fenwick<int> f(n + 1);
  auto update = [&](int x, int c) {
    f.add(t.tin[x], +c);
    f.add(t.tout[x], -c);
  };
  auto get = [&](int x) {
    int r = x;
    for (int i = t.maxup; i >= 0; --i) {
      int y = t.up[i][r];
      if (f.sum(t.dfn[x] + 1) - f.sum(t.dfn[y] + 1) >= t.dep[x] - t.dep[y]) {
        r = y;
      }
    }
    return r;
  };

  vector<bool> open(n);
  vector<int> pre(n), cnt(n, 1);

  while (m--) {
    int i;
    cin >> i;
    --i;
    auto [x, y] = e[i];
    int r = get(x);
    if (open[i]) {
      pre[i] = cnt[y] = cnt[r];
      update(y, -1);
    } else {
      cnt[r] = cnt[r] + cnt[y] - pre[i];
      update(y, +1);
    }
    open[i] = !open[i];
  }

  while (q--) {
    int x;
    cin >> x;
    --x;
    cout << cnt[get(x)] << "\n";
  }

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 616 KB Output is correct
7 Correct 9 ms 2152 KB Output is correct
8 Correct 9 ms 2152 KB Output is correct
9 Correct 9 ms 2152 KB Output is correct
10 Correct 137 ms 19272 KB Output is correct
11 Correct 131 ms 19164 KB Output is correct
12 Correct 177 ms 28576 KB Output is correct
13 Correct 70 ms 19084 KB Output is correct
14 Correct 84 ms 18136 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23772 KB Output is correct
2 Correct 70 ms 23516 KB Output is correct
3 Correct 73 ms 27804 KB Output is correct
4 Correct 72 ms 27764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 13 ms 3164 KB Output is correct
8 Correct 216 ms 29132 KB Output is correct
9 Correct 216 ms 29136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 29132 KB Output is correct
2 Correct 112 ms 28880 KB Output is correct
3 Correct 122 ms 29072 KB Output is correct
4 Correct 119 ms 28952 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 12 ms 2272 KB Output is correct
7 Correct 182 ms 19664 KB Output is correct
8 Correct 217 ms 29364 KB Output is correct
9 Correct 98 ms 20220 KB Output is correct
10 Correct 109 ms 19408 KB Output is correct
11 Correct 98 ms 24972 KB Output is correct
12 Correct 95 ms 24784 KB Output is correct
13 Correct 120 ms 29048 KB Output is correct