Submission #1203944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203944		akamizane	Synchronization (JOI13_synchronization)	C++20	100 / 100	196 ms	31748 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
const int N = 2e5 + 5;

int n, m, q, in[N], it, sz[N], head[N], pos[N], res[N], pre[N], depth[N], up[N][25];
bool status[N];
ii edge[N];
vector<int> ad[N];

void dfs(int u, int p){
  in[u] = ++it;
  sz[u] = 1;
  for(int i = 1; i <= 17; i++) up[u][i] = up[up[u][i - 1]][i - 1];

  for(auto v : ad[u]) if(v != p){
    up[v][0] = u;
    depth[v] = depth[u] + 1;
    dfs(v, u);
    sz[u] += sz[v];
  }
}

void HLD(int u, int p){
  if(!head[u]) head[u] = u;
  pos[u] = ++it;
  sort(ad[u].begin(), ad[u].end(), [&](int x, int y){
          return sz[x] > sz[y];
       });
  int skip = false;
  for(auto v : ad[u]) if(v != p){
    if(!skip) head[v] = head[u], skip = true;
    HLD(v, u);
  }
}

int bit[N];
void update(int i, int x){
  for(; i <= n; i += i & -i) bit[i] += x;
}
int get(int i){
  int res = 0;
  for(; i > 0; i -= i & -i) res += bit[i];
  return res;
}

int root(int u){
  while(u){
    if(get(pos[u]) - get(pos[head[u]] - 1) == depth[u] - depth[head[u]] + 1){
      u = up[head[u]][0];
      continue;
    }
    for(int i = 17; i >= 0; i--) if(up[u][i] && head[u] == head[up[u][i]])
      if(get(pos[u]) - get(pos[up[u][i]]) == depth[u] - depth[up[u][i]]) u = up[u][i];
    return u;
  }
  return 1;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m >> q;
  for(int i = 1; i < n; i++){
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
    edge[i] = {u, v};
  }
  it = 0; dfs(1, -1);
  it = 0; HLD(1, -1);

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

  while(m--){
    int e; cin >> e;
    auto [u, v] = edge[e];

    status[e] ^= 1;
    if(status[e]){
      update(pos[v], 1);
      u = root(u);
      res[u] += res[v] - pre[e];
    }else{
      update(pos[v], -1);
      u = root(u);
      res[v] = pre[e] = res[u];
    }
  }
  while(q--){
    int u; cin >> u;
    cout << res[root(u)] << "\n";
  }

  return 0;
}

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