Submission #1203943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203943		akamizane	Synchronization (JOI13_synchronization)	C++20	100 / 100	208 ms	35260 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif

#define int long long 

const int maxn = 1e5 + 5;

int n, m, q, tin[maxn], tout[maxn], bit[maxn], up[maxn][20], sz[maxn], same[maxn], active[maxn], timeDfs = 1;
pair<int, int> edge[maxn];
vector<int> ad[2 * maxn];

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

int get(int k){
   int ans = 0;
   for (; k; k -= k & -k) ans += bit[k];
   return ans;
}

void dfs(int u, int p){
   tin[u] = timeDfs++;
   up[u][0] = p;
   for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
   sz[u] = 1;
   for (auto v : ad[u]){
      if (v == p) continue;
      dfs(v, u);
   }
   tout[u] = timeDfs;
}

int anc(int u){
   int node = u;
   for (int i = 19; i >= 0; i--){
      if (get(tin[up[node][i]]) == get(tin[u])) node = up[node][i];
   }
   return node;
}

void solve(){
   cin >> n >> m >> q;
   for (int i = 1; i <= n - 1; i++){
      int u, v;
      cin >> u >> v;
      edge[i] = {u, v};
      ad[u].push_back(v);
      ad[v].push_back(u);
   }
   dfs(1, 0);
   for (int i = 1; i <= n; i++){
      update(tin[i], -1);
      update(tout[i], 1);
   }
   while(m--){
      int idx;
      cin >> idx;
      auto& [u, v] = edge[idx];
      if (up[u][0] == v) swap(u, v);
      if (active[idx]){
         sz[v] = same[v] = sz[anc(u)];
         update(tin[v], -1);
         update(tout[v], 1);
      }
      else{
         sz[anc(u)] += sz[v] - same[v];
         update(tin[v], 1);
         update(tout[v], -1);
      }
      active[idx] ^= 1;
   }
   while(q--){
      int x;
      cin >> x;
      cout << sz[anc(x)] << "\n";
   }
}

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int tt = 1;
   // cin >> tt;
   while(tt--) {
      solve();
   }
   return 0;
}

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