Submission #1188246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188246		_ncng.nyr	Synchronization (JOI13_synchronization)	C++20	100 / 100	307 ms	26516 KiB

synchronization

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, k, timer, it;
int in[N], out[N], rev[N], state[N], ans[N], par[N], pre[N], h[N];
int chain[N], boss[N], sz[N], mk[N];
int up[20][N];
pair<int, int> e[N];
vector<int> ad[N];

struct BIT {
  int bit[N];

  void upd (int i, int x) {
    for (; i <= n; i += i & -i) bit[i] += x;
  }

  int get (int i) {
    int ret = 0;
    for (; i; i -= i & -i) ret += bit[i];
    return ret;
  }
} st;

void pre_dfs (int u, int p) {
  sz[u] = 1;
  for (auto v : ad[u]) if (v != p) {
    par[v] = u;
    h[v] = h[u] + 1;
    pre_dfs(v, u); sz[u] += sz[v];
  }
}

void hld (int u, int p) {
  in[u] = ++timer;
  if (!boss[it]) boss[it] = u;
  chain[u] = it;

  if (!p) for (int i = 0; i <= 18; ++i) up[i][u] = u;
  else {
    up[0][u] = p;
    for (int i = 1; i <= 18; ++i) up[i][u] = up[i - 1][up[i - 1][u]];
  }

  int nxt = 0;
  for (auto v : ad[u]) if (v != p && sz[v] > sz[nxt]) nxt = v;
  if (nxt) hld(nxt, u);

  for (auto v : ad[u]) if (v != p && v != nxt) {
    ++it; hld(v, u);
  }
  out[u] = timer;
}

bool anc (int u, int v) {
  return (in[u] <= in[v] && out[v] <= out[u]);
}

int fin (int v, int u) {
  for (int k = 18; k >= 0; --k) if (anc(u, up[k][v]))
    if (st.get(in[v]) - st.get(in[up[k][v]]) == h[v] - h[up[k][v]]) v = up[k][v];
  return v;
}

int root (int v) {
  while (1) {
    int head = boss[chain[v]];
    if (head == 1) return fin(v, 1);
    if (st.get(in[v]) - st.get(in[head]) == h[v] - h[head]) {
      if (mk[head]) v = par[head];
      else return head;
    }
    else return fin(v, head);
  }
}

int32_t main() {
  cin.tie(0) -> sync_with_stdio(0);

  #define task "Synchronization"

  if (fopen ("task.inp", "r")) {
    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);
  }

  if (fopen (task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
    e[i] = {u, v};
  }
  pre_dfs(1, 0); hld(1, 0);

  for (int i = 1; i < n; ++i) {
    auto [u, v] = e[i];
    if (in[u] > in[v]) swap(u, v);
    e[i] = {u, v};
  }

  for (int i = 1; i <= n; ++i) ans[i] = 1;

  for (int i = 1; i <= m; ++i) {
    int id; cin >> id;
    state[id] ^= 1;
    auto [u, v] = e[id];
    mk[v] ^= 1;

    if (state[id]) {
      int head = root(u);
      ans[head] = ans[head] + ans[v] - pre[id];
      st.upd(in[v], 1);
    }
    else {
      int head = root(u);
      pre[id] = ans[v] = ans[head];
      st.upd(in[v], -1);
    }
  }

  while (k--) {
    int u; cin >> u;
    cout << ans[root(u)] << '\n';
  }
}

Compilation message (stderr)

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:86:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen ("task.inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:87:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen ("task.out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:91:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:92:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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