Submission #1257846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257846		nai0610	Synchronization (JOI13_synchronization)	C++20	100 / 100	230 ms	23624 KiB

synchronization

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,m,q,tin[maxn],tout[maxn],cur;
pair<int,int> e[maxn];
vector<int> g[maxn];
int h[maxn],st[maxn][20];
int bit[maxn],res[maxn],pre[maxn];
bool has[maxn];
void update(int i,int x) {
	for (;i<=n;i+=i&-i) bit[i]+=x;
}
int query(int i){
	int res=0;
	for (;i>0;i-=i&-i) res+=bit[i];
	return res;
}
void dfs(int u){
	tin[u]=++cur;
	for (auto v:g[u]) {
		if (st[u][0]==v) continue;
		h[v]=h[u]+1;
		st[v][0]=u;
		for (int i=1;i<=17;i++) st[v][i]=st[st[v][i-1]][i-1];
		dfs(v);
	}
	tout[u]=cur;
}
int calc(int u){
	int cur=query(tin[u]);
	for (int i=17;i>=0;i--) {
		int val=query(tin[st[u][i]]);
		if ((cur-val)&(1<<i)) {
			cur=val;
			u=st[u][i];
		}
	}
	return u;
}
void up(int id) {
	int u=e[id].first,v=e[id].second;
	if (h[u]>h[v]) swap(u,v);
	int w=calc(u);
	if (!has[id]) {
		res[w]+=res[v]-pre[v];
		update(tin[v],1);
		update(tout[v]+1,-1);
	}
	else{
		res[v]=pre[v]=res[w];
		update(tin[v],-1);
		update(tout[v]+1,1);
	}
	has[id]^=1;
}
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	cin>>n>>m>>q;
	for (int i=1;i<=n;i++) res[i]=1;
	for (int i=1;i<n;i++) {
		int u,v;
		cin >>u>>v;
		e[i]={u,v};
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	while (m--) {
		int id;
		cin >>id;
		up(id);
	}
	for (int i=1;i<n;i++) {
		if (has[i]) up(i);
	}
	while (q--) {
		int u;cin >>u;
		cout <<res[u]<<'\n';
	}
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\n';
    return 0;
}

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