Submission #1128317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128317		idiotcomputer	Synchronization (JOI13_synchronization)	C++17	100 / 100	212 ms	26952 KiB

synchronization

#include <bits/stdc++.h>
#include <system_error>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define sz(x) (int) (x).size()

const int mxN = 1e5+5;
int N,M,Q;

vector<int> adj[mxN];
pii edges[mxN];
bool act[mxN];
int ve[mxN];

int d[mxN];
int ss[mxN];
int p[mxN];
//depth then node
set<pii> hp[mxN];
int hidx[mxN];
int root[mxN];

void dfs(int node, int cp = -1, int dep = 0){
	d[node] = dep;
	ss[node] = 1;
	p[node] = cp;
	for (int i : adj[node]){
		if (i == cp) continue;
		dfs(i,node,dep+1);
		ss[node] += ss[i];
	}
}

int cnt = 0;	
void dfs2(int node){
	hidx[node] = cnt;
	hp[hidx[node]].insert({-d[node],node});
	pii cm = {-1, -1};
	for (int i : adj[node]){
		if (i == p[node]) continue;
		if (ss[i] > cm.f) cm = {ss[i], i};
	}

	for (int i : adj[node]){
		if (i != cm.s) continue;
		dfs2(i);
	}

	for (int i : adj[node]){
		if (i == cm.s || i == p[node]) continue;
		cnt++;
		root[cnt] = i;
		dfs2(i);
	}
}

int g_root(int node){
	while (1){
		auto it = hp[hidx[node]].lower_bound({-d[node],-1});
		if (it != hp[hidx[node]].end()) return (*it).s;
		node = root[hidx[node]];
		node = p[node];
	}
}

int dp[mxN];
//changing edge i
void solve(int i){
	int u = edges[i].f;
	int v = edges[i].s;
	if (d[u] < d[v]) swap(u,v);

	if (act[i]){
		//deactivating edge 
		int r = g_root(v);
		dp[u] = dp[r];
		ve[i] = dp[r];
		act[i] = 0;
		hp[hidx[u]].insert({-d[u],u});
	} else {
		//activating edge
		int r1 = g_root(u);
		int r2 = g_root(v);
		int nv = dp[r1] + dp[r2] - ve[i];
		dp[r2] = nv;
		act[i] = 1;
		hp[hidx[u]].erase({-d[u],u});
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> Q;
	int u,v;
	for (int i = 0; i < N-1; i++){
		cin >> u >> v;
		u--;
		v--;
		adj[u].pb(v);
		adj[v].pb(u);
		edges[i] = {u,v};
		ve[i] = 0;
	}
	dfs(0);
	root[0] = 0;
	dfs2(0);

	for (int i = 0; i < N; i++) dp[i] = 1;
	memset(act,0,sizeof(act));
	
	for (int i = 0; i < M; i++){
		cin >> u;
		solve(u-1);
		//for (int j = 0; j < N; j++) cout << dp[j] << " ";
		//cout << '\n';
	}


/*	cout << "DONE---\n";
	for (int i = 0; i < N; i++) cout << hidx[i] << " ";
	cout << '\n';
	for (int i = 0; i <= cnt; i++){
		for (pii c : hp[i]) cout << c.f << ',' << c.s << " ";
		cout << '\n';
	}*/
	for (int i = 0; i < Q; i++){
		cin >> u;
		u--;
		int r = g_root(u);

		cout << dp[r] << "\n";
	}

	return 0;
}

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