Submission #1072992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072992		pubin06	Synchronization (JOI13_synchronization)	C++14	100 / 100	408 ms	21768 KiB

synchronization

#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 100005;

int n, m, q;
pair<int, int> e[MXn];
vector<int> adj[MXn];
int up0[MXn], sz[MXn];
void DFS(int u, int par) {
	sz[u] = 1;
	for (int v: adj[u]) if (v != par) {
		up0[v] = u;
		DFS(v, u);
		sz[u] += sz[v];
	}
}
int head[MXn], st[MXn], timer = 0, ord[MXn];
void HLD(int u, int par, int he) {
	st[u] = ++timer;
	ord[st[u]] = u;
	head[u] = he;
	pair<int, int> best = {-1, -1};
	for (int v: adj[u]) if (v != par) {
		best = max(best, {sz[v], v});
	}
	if (best.se > 0) {
		HLD(best.se, u, he);
		for (int v: adj[u]) if (v != par && v != best.se) {
			HLD(v, u, v);
		}
	}
}

int ST[1 << 18] = {0};
void update(int i) {
	int id = 1, l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (i <= mid) {
			id <<= 1;
			r = mid;
		} else {
			id = id << 1 | 1;
			l = mid + 1;
		}
	}
	ST[id] ^= 1;
	while (id > 1) {
		id >>= 1;
		ST[id] = min(ST[id << 1], ST[id << 1 | 1]);
	}
}
int get(int Lf, int Rt, int id = 1, int l = 1, int r = n) {
	if (Lf <= l && r <= Rt) return ST[id];
	int mid = (l + r) >> 1, res = 1;
	if (Lf <= mid) res = min(res, get(Lf, Rt, id << 1, l, mid));
	if (mid < Rt) res = min(res, get(Lf, Rt, id << 1 | 1, mid + 1, r));
	return res;
}

int mark[MXn] = {0};
int find(int u) {
	// int cc = u;
	// if (cc == 5) cerr << "[";
	while (mark[u]) {
		if (get(st[head[u]], st[u])) {
			u = head[u];
			// if (cc == 5) cerr << "0" << u << ' ';
		} else {
			int pos = 0;
			int l = st[head[u]], r = st[u], mid;
			while (l <= r) {
				mid = (l + r) >> 1;
				if (get(mid, st[u])) {
					pos = mid;
					r = mid - 1;
				} else l = mid + 1;
			}
			u = ord[pos];
			// if (cc == 5) cerr << "00" << u << ' ';
		}
		u = up0[u];
	}
	// if (cc == 5) cerr << "]";
	return u;
}
int ans[MXn], last[MXn]; // last[id] là số thông tin mà tplt chứa cạnh thứ id có, tính đến thời điểm cuối cùng đến hiện tại nó còn được nối

signed main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> q;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
		e[i] = {u, v};
	}
	DFS(1, 0);
	HLD(1, 0, 1);
	// for (int i = 1; i <= n; i++) cerr << head[i] << ' ';
	// cerr << '\n';
	// for (int i = 1; i <= n; i++) cerr << st[i] << ' ';
	// cerr << '\n';
	// cerr << '\n';
	
	for (int u = 1; u <= n; u++) ans[u] = 1;
	while (m--) {
		int id; cin >> id;
		if (up0[e[id].fi] == e[id].se) swap(e[id].fi, e[id].se);
		if (!mark[e[id].se]) {
			ans[find(e[id].fi)] += ans[e[id].se] - last[id];
		} else {
			ans[e[id].se] = last[id] = ans[find(e[id].fi)];
		}
		mark[e[id].se] ^= 1;
		update(st[e[id].se]);
		// for (int i = 1; i <= n; i++) cerr << find(i) << ' ';
		// cerr << '\n';
	}
	for (int i = 1; i <= n; i++) ans[i] = ans[find(i)];
	while (q--) {
		int u; cin >> u; cout << ans[u] << '\n';
	}
	
	return 0;
}

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