Submission #520255

#	Time	Username	Problem	Language	Result	Execution time	Memory
520255		blue	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1094 ms	25368 KiB

cleaning

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 100'000;
const int lg = 17;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

vi edge[1+mx];
vvi anc(1+mx, vi(1+lg, 0));

vi order(1, 0);
vi order_index(1+mx, 0);
vi depth(1+mx, 0);

vi leaf(1+mx, 0);
vi st_leaf(1+mx, 0);

void dfs(int u)
{
	order_index[u] = sz(order);
	order.push_back(u);

	st_leaf[u] = leaf[u];

	for(int v: edge[u])
	{
		if(anc[u][0] == v) continue;
		depth[v] = 1 + depth[u];
		anc[v][0] = u;
		dfs(v);

		st_leaf[u] += st_leaf[v];
	}
}

int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1<<e))
			u = anc[u][e];

	return u;
}

int lca(int u, int v)
{
	if(depth[v] < depth[u]) swap(u, v);
	v = ancestor(v, depth[v] - depth[u]);
	if(u == v) return u;

	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] == anc[v][e]) continue;
		u = anc[u][e];
		v = anc[v][e];
	}
	return u;
}

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

	int N, Q;
	cin >> N >> Q;

	for(int e = 1; e <= N-1; e++)
	{
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	for(int i = 1; i <= N; i++)
		if(sz(edge[i]) == 1)
			leaf[i] = 1;

	int rt = 1;
	while(leaf[rt]) rt++;


	dfs(rt);

	for(int e = 1; e <= lg; e++)
		for(int i = 1; i <= N; i++) 
			anc[i][e] = anc[ anc[i][e-1] ][e-1];

	// cerr << "root = " << rt << '\n';

	// for(int i = 1; i <= N; i++) cerr << i << " : " << leaf[i] << ' ' << st_leaf[i] << '\n';

	int leafcount = st_leaf[rt];


	for(int q = 1; q <= Q; q++)
	{
		int D;
		cin >> D;

		vi new_leaf = leaf;
		vi new_st_leaf = st_leaf;

		int new_leafcount = leafcount;

		int extra_odd = 0;

		vi node_delta(1+N, 0);

		vi a(1+D);

		for(int d = 1; d <= D; d++)
		{
			cin >> a[d];

			if(leaf[a[d]])
			{
				leaf[a[d]] = 0;
				new_leafcount--;
			}
			new_leafcount++;









			int delta = 0;

			if(new_leaf[a[d]])
			{
				new_leaf[a[d]] = 0;
				// new_st_leaf[a]--;
				delta--;
			}

			delta++;
			extra_odd++;

			// for(int z = a; z != 0; z = anc[z][0])
			// {
			// 	new_st_leaf[z] += delta;
			// }

			node_delta[a[d]] += delta;

			// cerr << a << " : " << "delta = " << delta << '\n';
		}

		for(int d = 1; d <= D; d++)
				leaf[a[d]] = sz(edge[a[d]]) == 1;

		for(int oi = N; oi >= 1; oi--)
		{
			int u = order[oi];
			for(int v: edge[u])
			{
				if(order_index[v] > order_index[u])
					node_delta[u] += node_delta[v];
			}
		}

		// for(int i = 1; i <= N; i++) cerr << i << " : " << new_leaf[i] << ' ' << new_st_leaf[i] << '\n';

		if(new_leafcount % 2 == 1) cout << "-1\n";
		else
		{
			int ans = extra_odd;
			for(int i = 1; i <= N; i++)
				if(i != rt)
					ans += vi{2, 1}[(new_st_leaf[i] + node_delta[i]) % 2];

			cout << ans << '\n';
		}
	}
}

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