Submission #598238

#	Time	Username	Problem	Language	Result	Execution time	Memory
598238		penguinhacker	Synchronization (JOI13_synchronization)	C++17	100 / 100	280 ms	26888 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], edge[mxN], last[mxN], ans[mxN], tin[mxN], tout[mxN], t, d[mxN], anc[mxN][17], ft[2*mxN+1];
vector<int> adj[mxN];
bool active[mxN];

void dfs(int u=0) {
	tin[u]=t++;
	for (int i=1; i<17; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int i : adj[u]) {
		int v=eu[i]^ev[i]^u;
		if (v!=anc[u][0]) {
			d[v]=d[u]+1, anc[v][0]=u;
			edge[i]=v;
			dfs(v);
		}
	}
	tout[u]=t++;
}

void upd(int i, int x) {
	for (++i; i<=2*n; i+=i&-i)
		ft[i]+=x;
}

int qry(int i) {
	int r=0;
	for (++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

int get_head(int u) {
	for (int i=16; ~i; --i)
		if (qry(tin[u])-qry(tin[anc[u][i]])==(1<<i))
			u=anc[u][i];
	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];
		if (!active[u]) { // activate edge between u-p[u]
			int v=get_head(anc[u][0]);
			ans[v]+=ans[u]-last[u];
			//cout << v << " " << qry(tin[p[u]]) << endl;
		} else {
			ans[u]=ans[get_head(u)];
			last[u]=ans[u];
			//cout << get_head(u) << endl;
		}
		upd(tin[u], active[u]?-1:1);
		upd(tout[u], active[u]?1:-1);
		active[u]^=1;
	}
	while(q--) {
		int u;
		cin >> u, --u;
		cout << ans[get_head(u)] << "\n";
	}
	return 0;
}

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