Submission #714910

#	Time	Username	Problem	Language	Result	Execution time	Memory
714910		study	Synchronization (JOI13_synchronization)	C++17	100 / 100	752 ms	28264 KiB

synchronization

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

const int N = 1e5;

vector<int> adj[N];
int tin[N],tout[N],segt[2*N],pere[20][N],res[N],status[N],depth[N],sync[N],queries[N];
int t = 0;

void dfs(int node, int p, int d){
	tin[node] = t;
	depth[node] = d;
	t++;
	for (int i:adj[node]){
		if (i != p){
			pere[0][i] = node;
			dfs(i,node,d+1);
		}
	}
	tout[node] = t;
}

void modify(int node, int val){
	node += N;
	segt[node] += val;
	node >>= 1;
	while (node){
		segt[node] = segt[2*node]+segt[2*node+1];
		node >>= 1;
	}
}

int query(int deb, int fin){
	deb += N;
	fin += N;
	int ans = 0;
	while (deb <= fin){
		if (deb&1){
			ans += segt[deb];
			deb++;
		}
		if (fin%2 == 0){
			ans += segt[fin];
			fin--;
		}
		deb >>= 1;
		fin >>= 1;
	}
	return ans;
}

int getRoot(int node){
	for (int i=19; i>=0; --i){
		if (query(tin[pere[i][node]]+1,tin[node]) == 0){
			node = pere[i][node];
		}
	}
	return node;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	vector<pair<int,int>> edges;
	for (int i=1; i<n; ++i){
		int u,v;
		cin >> u >> v;
		u--; v--;
		edges.emplace_back(u,v);
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	vector<int> event;
	for (int i=0; i<m; ++i){
		int a;
		cin >> a;
		a--;
		event.emplace_back(a);
	}
	for (int i=0; i<q; ++i){
		cin >> queries[i];
		--queries[i];
	}
	int root = 0;
	pere[0][root] = root;
	dfs(root,-1,0);
	for (int i=0; i<n; ++i){
		modify(tin[i],1);
		modify(tout[i],-1);
		res[i] = 1;
		status[i] = 0;
	}
	for (int i=1; i<20; ++i){
		for (int node=0; node<n; ++node){
			pere[i][node] = pere[i-1][pere[i-1][node]];
		}
	}
	for (int i=0; i<m; ++i){
		int u = edges[event[i]].first, v = edges[event[i]].second;
		if (depth[u] > depth[v]) swap(u,v);
		if (status[v] == 1){
			modify(tin[v],1);
			modify(tout[v],-1);
			u = getRoot(u);
			sync[v] = res[v] = res[u];
		}
		else{
			modify(tin[v],-1);
			modify(tout[v],1);
			u = getRoot(u);
			res[v] = res[u] = sync[v] = res[u]+res[v]-sync[v];
		}	
		status[v] = 1-status[v];
	}
	for (int i=0; i<q; ++i){
		cout << res[getRoot(queries[i])] << '\n';
	}
	return 0;
}

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