Submission #88106

#	Time	Username	Problem	Language	Result	Execution time	Memory
88106		KCSC	Synchronization (JOI13_synchronization)	C++14	100 / 100	687 ms	68468 KiB

synchronization

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

const int DIM = 100005;

int sgt[DIM * 8], fst[DIM], lst[DIM], oans[DIM], nans[DIM], lev[DIM];
vector<int> edg[DIM]; pair<int, int> lis[DIM]; bitset<DIM> oki;

void dfs(int x, int f) {
	static int cnt = 0;
	fst[x] = ++cnt; lev[x] = lev[f] + 1;
	for (int y : edg[x]) { 
		if (y != f) { 
			dfs(y, x); } }
	lst[x] = ++cnt; }

void update(int nd, int le, int ri, int ps, int vl) {
	if (le == ri) {
		sgt[nd] += vl; }
	else {
		int md = (le + ri) / 2;
		if (ps <= md) {
			update(nd << 1, le, md, ps, vl); }
		else {
			update(nd << 1 | 1, md + 1, ri, ps, vl); }
		if (lst[sgt[nd << 1]] > lst[sgt[nd << 1 | 1]]) {
			sgt[nd] = sgt[nd << 1]; }
		else {
			sgt[nd] = sgt[nd << 1 | 1]; } } }

int find(int nd, int le, int ri, int ps, int vl) {
	if (ps < le or (ri <= ps and lst[sgt[nd]] < lst[vl])) {
		return 0; }
	if (le == ri) {
		return sgt[nd]; }
	int md = (le + ri) / 2,
		rt = find(nd << 1 | 1, md + 1, ri, ps, vl);
	if (rt) {
		return rt; }
	else {
		return find(nd << 1, le, md, ps, vl); } }
	
int main(void) {
#ifdef HOME
	freopen("synchronization.in", "r", stdin);
	freopen("synchronization.out", "w", stdout);
#endif
	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int x, y; cin >> x >> y;
		edg[x].push_back(y); edg[y].push_back(x);
		lis[i] = make_pair(x, y); }
	dfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		update(1, 1, n << 1, fst[i], i); nans[i] = 1; }
	while (m--) {
		int id; cin >> id;
		int x = lis[id].first, y = lis[id].second;
		if (lev[x] > lev[y]) {
			swap(x, y); }
		int z = find(1, 1, n << 1, fst[x], x);
		if (!oki[id]) {
			nans[z] += nans[y] - oans[y];
			update(1, 1, n << 1, fst[y], -y); }
		else {
			nans[y] = nans[z];
			update(1, 1, n << 1, fst[y], y); }
		oans[y] = nans[y]; oki[id] = oki[id] ^ 1; }
	while (q--) {
		int x; cin >> x;
		cout << nans[find(1, 1, n << 1, fst[x], x)] << "\n"; }
	return 0; }

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