Submission #712732

#	Time	Username	Problem	Language	Result	Execution time	Memory
712732		study	Synchronization (JOI13_synchronization)	C++17	0 / 100	8100 ms	26796 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];
int t = 0;

void dfs(int node, int p){
	tin[node] = t;
	t++;
	for (int i:adj[node]){
		if (i != p){
			pere[0][i] = node;
			dfs(i,node);
		}
	}
	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--;
		}
	}
	return ans;
}

int getRoot(int node){
	for (int i=19; i>=0; --i){
		if (query(tin[node],tin[pere[i][node]]-1) == 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;
		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);
	}
	int root = 0;
	for (int i=0; i<q; ++i){
		cin >> root;
	}
	root--;
	for (int i=0; i<n; ++i){
		modify(i,1);
		res[i] = 1;
		status[i] = 1;
	}
	dfs(root,-1);
	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;
		modify(i,1-status[v]);
		status[v] = 1-status[v];
		modify(i,1-status[u]);
		status[u] = 1-status[u];
		if (status[i] == 1){
			res[getRoot(u)] += res[v];
			res[v] = 0;
		}
	}
	cout << res[getRoot(root)];
	return 0;
}

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