Submission #1059547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059547		nima_aryan	Synchronization (JOI13_synchronization)	C++17	100 / 100	223 ms	29364 KiB

synchronization

/**
 *    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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40