Submission #598223

#	Time	Username	Problem	Language	Result	Execution time	Memory
598223		penguinhacker	Synchronization (JOI13_synchronization)	C++17	40 / 100	8067 ms	17564 KiB

synchronization

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, q, eu[mxN], ev[mxN], p[mxN], edge[mxN], last[mxN], ans[mxN];
vector<int> adj[mxN];
bool active[mxN];

void dfs(int u=0) {
	for (int i : adj[u]) {
		int v=eu[i]^ev[i]^u;
		if (v!=p[u]) {
			p[v]=u;
			edge[i]=v;
			dfs(v);
		}
	}
}

int get_head(int u) {
	for (; u&&active[u]; u=p[u]);
	return u;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i=1; i<n; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	dfs();
	fill(ans, ans+n, 1);
	while(m--) {
		int u;
		cin >> u;
		u=edge[u];
		//cout << "activatting " << u << endl;
		if (!active[u]) { // activate edge between u-p[u]
			int v=get_head(p[u]);
			ans[v]+=ans[u]-last[u];
		} else {
			ans[u]=ans[get_head(u)];
			last[u]=ans[u];
		}
		active[u]^=1;
	}
	while(q--) {
		int u;
		cin >> u, --u;
		cout << ans[get_head(u)] << "\n";
	}
	return 0;
}

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