Submission #543136

#	Time	Username	Problem	Language	Result	Execution time	Memory
543136		sidon	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	184 ms	26272 KiB

cleaning

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

const int Z = 1e5, B = 17;

int N, Q;
vector<int> g[Z], h[Z];
int p[Z][B], L[Z], R[Z], s[Z], d[Z], dfsTimer, rt, leafCnt, ext;

void init(int u) {
	L[u] = dfsTimer++;
	for(int i = 0; i + 1 < B; ++i)
		p[u][i+1] = p[p[u][i]][i];

	s[u] = size(g[u]) > 1;
	leafCnt += !s[u];

	for(const int &v : g[u]) if(v != p[u][0]) {
		p[v][0] = u;
		d[v] = d[u] + 1;
		init(v);
		s[u] ^= s[v] ^ 1;
	}
	if(u != rt) ext += s[u];
	R[u] = dfsTimer++;
}

void dfs(int u) {
	for(const int &v : g[u]) if(v != p[u][0])
		s[v] += s[u], dfs(v);
}

#define isAncestor(U, V) (L[U] < L[V] && R[V] < R[U])

int lca(int u, int v) {
	if(isAncestor(u, v)) return u;
	for(int i = B; i--; ) if(!isAncestor(p[u][i], v)) u = p[u][i];
	return p[u][0];
}

int diff, c[Z];
void calc(int u, int par) {
	for(const int &v : h[u]) if(v != par) {
		calc(v, u);
		c[u] ^= c[v];
	}
	if(c[u]) {
		diff += (d[u] - d[par]) - 2 * (s[u] - s[par]);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> Q;
	for(int i = 1; i < N; ++i) {
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(; size(g[rt]) < 2; ++rt);

	p[rt][0] = rt;
	init(rt);
	dfs(rt);

	while(Q--) {
		int D; cin >> D;
		int leafDiff = diff = 0;

		vector<int> a(D);

		for(int &u : a)	{
			cin >> u;
			if(size(g[--u]) < 2) leafDiff += !c[u]++;
		}
		for(int &u : a)	c[u] = !!c[u] ^ 1;

		for(int t : {1, 0}) {
			sort(begin(a), end(a), [&](const int &i, const int &j) {
				return L[i] < L[j];
			});
			if(t) for(int i = D; --i; )
				a.push_back(lca(a[i], a[i-1]));
		}
		a.erase(unique(begin(a), end(a)), end(a));
		vector<int> st;

		for(const int &u : a) {
			if(!empty(st)) {
				for(; !isAncestor(st.back(), u); st.pop_back());
				h[st.back()].push_back(u);
			}
			st.push_back(u);
		}
		calc(a[0], rt);
		for(const int &u : a) {
			h[u].clear();
			c[u] = 0;
		}

		cout << ((leafCnt + D - leafDiff) & 1 ? -1 : N - 1 + D + ext + diff) << '\n';
	}
}

• 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