Submission #1172687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172687		Troll321	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	137 ms	43028 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;

ll n, q, d, initAns, ans = 0, root, parr[MAXN], query[MAXN], plusarr[MAXN];
bool parity[MAXN], isLeaf[MAXN], processed[MAXN];
vector<ll> adjl[MAXN];

ll sz[MAXN], depth[MAXN], heavy[MAXN];
struct segment {
	ll root = 0;
	vector<ll> nodes, seg, lazy;

	ll getIdx(ll node) {
		return depth[node] - depth[root];
	}

	ll lb() {return 0;}
	ll rb() {return (ll)nodes.size()-1;}

	void addNode(ll node) {
		if(nodes.empty()) {root = node;}
		nodes.push_back(node);
	}

	void build(ll pos, ll l, ll r) {
		lazy[pos] = 0;
		if(l == r) {
			seg[pos] = (parity[nodes[l]]^1);
			return ;
		}
		ll mid = (l+r)/2;
		build(pos*2, l, mid);
		build(pos*2+1, mid+1, r);
		seg[pos] = seg[pos*2] + seg[pos*2+1];
	}

	void init() {
		seg.resize(nodes.size()*4);
		lazy.resize(nodes.size()*4);
		build(1, lb(), rb());
	}

	void updateLazy(ll pos, ll l, ll r) {
		if(lazy[pos] % 2 == 1) {
			seg[pos] = (r-l+1) - seg[pos];
		}

		if(l != r) {
			lazy[pos*2] += lazy[pos];
			lazy[pos*2+1] += lazy[pos];
		}

		lazy[pos] = 0;
	}

	void update(ll pos, ll l, ll r, ll a, ll b) {
		updateLazy(pos, l, r);
		if(l > b || r < a) {
			return ;
		}
		if(a <= l && r <= b) {
			seg[pos] = (r-l+1) - seg[pos];
			if(l != r) {
				lazy[pos*2]++;
				lazy[pos*2+1]++;
			}
			return ;			
		}
		ll mid = (l+r)/2;
		update(pos*2, l, mid, a, b);
		update(pos*2+1, mid+1, r, a, b);
		seg[pos] = seg[pos*2] + seg[pos*2+1];
	}

	ll query(ll pos, ll l, ll r, ll idxa, ll idxb) {
		if(l > idxb || r < idxa) {
			return 0;
		}
		
		updateLazy(pos, l, r);
		if(idxa <= l && r <= idxb) {
			return seg[pos];
		}
		ll mid = (l+r)/2;
		return (
			query(pos*2, l, mid, idxa, idxb) +
			query(pos*2+1, mid+1, r, idxa, idxb)
		);
	}
};

segment segs[MAXN];

void dfs(ll now, ll par) {
	parity[now] = 0;
	parr[now] = par;
	isLeaf[now] = (adjl[now].size() == 1);

	depth[now] = depth[par]+1;
	sz[now] = 1;
	if(isLeaf[now]) {parity[now] = 1;}
	else {
		for(ll nxt : adjl[now]) {
			if(nxt == par) {continue ;}
			dfs(nxt, now);
			parity[now] ^= parity[nxt];
			sz[now] += sz[nxt];
		}
	}

	if(parity[now] == 0) {ans++;}
}

void addHeavy(ll node, ll hidx) {
	segs[hidx].addNode(node);
}

void hld(ll now, ll par) {
	if(!heavy[now]) {
		heavy[now] = now;
		addHeavy(now, heavy[now]);
	}

	ll mx = -1, nowHeavy = -1;
	for(ll nxt : adjl[now]) {
		if(nxt == par) {continue ;}
		if(sz[nxt] > mx) {
			mx = sz[nxt];
			nowHeavy = nxt;
		}
	}

	if(nowHeavy != -1) {
		heavy[nowHeavy] = heavy[now];
		addHeavy(nowHeavy, heavy[now]);
	}

	for(ll nxt : adjl[now]) {
		if(nxt == par) {continue ;}
		hld(nxt, now);
	}
}

void initSegs() {
	for (int i = 1; i <= n; ++i) {
		if(segs[i].nodes.empty()) {continue ;}
		segs[i].init();
	}
}

void addLeaf(ll node) {
	segment* s;

	while(true) {
		s = &segs[heavy[node]];
		(*s).update(1, (*s).lb(), (*s).rb(), 0, (*s).getIdx(node));

		if((*s).root == root) {break ;}
		node = parr[(*s).root];
	}
}

ll ask(ll node) {
	segment* s;
	ll out = 0;
	while(true) {
		s = &segs[heavy[node]];
		out += (*s).query(1, (*s).lb(), (*s).rb(), 0, (*s).getIdx(node));

		if((*s).root == root) {break ;}
		node = parr[(*s).root];
	}

	return out;
}

ll getRoot() {
	segment *s = &segs[heavy[root]];
	return 1-(*s).query(1, (*s).lb(), (*s).rb(), 0, 0);
}

void build() {
	dfs(root, root);
	hld(root, root);
	initSegs();
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q;
	ans = n-1;
	for (int i = 0; i < n-1; ++i) {
		ll a, b;
		cin >> a >> b;
		adjl[a].push_back(b);
		adjl[b].push_back(a);

		if(adjl[a].size() > 1) {root = a;}
		else if(adjl[b].size() > 1) {root = b;}
	}

	build();

	initAns = ans;
	while(q--) {
		// Input
		ans = initAns;
		cin >> d;
		ans += d;
		for (int i = 0; i < d; ++i) {
			cin >> query[i];
			plusarr[query[i]]++;
		}

		for (int i = 0; i < d; ++i) {
			ll now = query[i];
			if(processed[now]) {continue ;}
			processed[now] = true;

			if((plusarr[now]-isLeaf[now]) % 2) {
				// cout << ans << " - " << now << " " << ask(now) << " ";
				ans -= ask(now);
				addLeaf(now);
				ans += ask(now);
				// cout << ask(now) << " - " << ans << "|\n";
			}
		}

		if(getRoot() == 1) {
			cout << "-1\n";
		} else {
			cout << (ans-1) << "\n";
		}

		// Reset
		for (int i = 0; i < d; ++i) {processed[query[i]] = false;}
		for (int i = 0; i < d; ++i) {
			ll now = query[i];
			if(processed[now]) {continue ;}
			processed[now] = true;

			if((plusarr[now]-isLeaf[now]) % 2) {
				addLeaf(now);
			}
		}
		for (int i = 0; i < d; ++i) {processed[query[i]] = false; plusarr[query[i]] = 0;}
	}
	return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30