oj.uz

Submission #520278

# Submission time Handle Problem Language Result Execution time Memory
520278 2022-01-29T05:33:54 Z blue Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 225 ms 27572 KB 
#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 anc[u][0];
}








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];





	int leafcount = st_leaf[rt];

	vi anc_even(1+N, 0);
	for(int u: order)
	{
		if(u == 0) continue;
		anc_even[u] = anc_even[ anc[u][0] ] + (st_leaf[u] % 2 == 0);
	}


	vi delta(1+N, 0);

	vi exists(1+N, 0);

	vi new_parent(1+N);


	int basicAns = 0;
	for(int i = 1; i <= N; i++)
	{
		if(i == rt) continue;
		if(st_leaf[i] % 2 == 0) basicAns += 2;
		else basicAns += 1;
	}


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

		int new_leafcount = leafcount;
 
		vi a(D);
 
		for(int d = 0; d < D; d++)
		{
			cin >> a[d];
 
			if(leaf[a[d]])
			{
				leaf[a[d]] = 0;
				new_leafcount--;
				delta[a[d]] ^= 1;
			}
			new_leafcount++;
			delta[a[d]] ^= 1;
		}
		// cerr << "read input\n";

		if(new_leafcount % 2 == 1) 
		{
			cout << "-1\n";
			for(int z: a) 
			{
				delta[z] = 0;
				leaf[z] = (sz(edge[z]) == 1);
			}
			continue;
		}


		int ans = D + basicAns;

		sort(a.begin(), a.end(), [] (int u, int v)
		{
			return order_index[u] < order_index[v];
		});

		for(int i = 0; i < D-1; i++)
			a.push_back(lca(a[i], a[i+1]));
		a.push_back(rt);

		vi a_unique;

		// cerr << "A\n";

		for(int z: a)
		{
			if(exists[z]) continue;
			exists[z] = 1;
			a_unique.push_back(z);
		}

		for(int z: a) exists[z] = 0;

		sort(a_unique.begin(), a_unique.end(), [] (int u, int v)
		{
			return order_index[u] < order_index[v];
		});	
	// cerr << "B\n";


		vi st{a_unique[0]};

		int aux_root = st[0];

		new_parent[aux_root] = 0;

		for(int y = 1; y < sz(a_unique); y++)
		{
			int u = a_unique[y];
			while(depth[u] <= depth[st.back()] || ancestor(u, depth[u] - depth[st.back()]) != st.back())
				st.pop_back();

			new_parent[u] = st.back();

			st.push_back(u);
		}
		// cerr << "C\n";

		sort(a_unique.begin(), a_unique.end(), [] (int u, int v)
		{
			return depth[u] > depth[v];
		});	

		// cerr << "au = ";
		// for(int au: a_unique) cerr << au << " " << delta[au] << '\n';

		for(int y = 0; y < sz(a_unique)-1; y++)
		{
			int u = a_unique[y];

			if(delta[u])
			{
				// cerr << "inverting path " << u << " to " << new_parent[u] << " with " << 
				ans += (depth[u] - depth[new_parent[u]]) - 2*(anc_even[u] - anc_even[new_parent[u]]);
			}

			delta[ new_parent[u] ] ^= delta[u];
		}
		// cerr << "D\n";


		for(int z: a) 
		{
			delta[z] = 0;
			leaf[z] = (sz(edge[z]) == 1);
		}

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14352 KB Output is correct
2 Correct 82 ms 15580 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15248 KB Output is correct
2 Correct 16 ms 14852 KB Output is correct
3 Correct 59 ms 19984 KB Output is correct
4 Correct 88 ms 19420 KB Output is correct
5 Correct 102 ms 21084 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15680 KB Output is correct
2 Correct 18 ms 15444 KB Output is correct
3 Correct 71 ms 25792 KB Output is correct
4 Correct 86 ms 26024 KB Output is correct
5 Correct 74 ms 24628 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16020 KB Output is correct
2 Correct 32 ms 15836 KB Output is correct
3 Correct 20 ms 15676 KB Output is correct
4 Correct 20 ms 16068 KB Output is correct
5 Correct 23 ms 16208 KB Output is correct
6 Correct 44 ms 16368 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18100 KB Output is correct
2 Correct 114 ms 17792 KB Output is correct
3 Correct 79 ms 17096 KB Output is correct
4 Correct 132 ms 19260 KB Output is correct
5 Correct 126 ms 19140 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 20192 KB Output is correct
2 Correct 143 ms 24404 KB Output is correct
3 Correct 147 ms 24276 KB Output is correct
4 Correct 140 ms 23992 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14352 KB Output is correct
2 Correct 82 ms 15580 KB Output is correct
3 Correct 32 ms 15248 KB Output is correct
4 Correct 16 ms 14852 KB Output is correct
5 Correct 59 ms 19984 KB Output is correct
6 Correct 88 ms 19420 KB Output is correct
7 Correct 102 ms 21084 KB Output is correct
8 Correct 25 ms 15680 KB Output is correct
9 Correct 18 ms 15444 KB Output is correct
10 Correct 71 ms 25792 KB Output is correct
11 Correct 86 ms 26024 KB Output is correct
12 Correct 74 ms 24628 KB Output is correct
13 Correct 44 ms 16020 KB Output is correct
14 Correct 32 ms 15836 KB Output is correct
15 Correct 20 ms 15676 KB Output is correct
16 Correct 20 ms 16068 KB Output is correct
17 Correct 23 ms 16208 KB Output is correct
18 Correct 44 ms 16368 KB Output is correct
19 Correct 76 ms 18100 KB Output is correct
20 Correct 114 ms 17792 KB Output is correct
21 Correct 79 ms 17096 KB Output is correct
22 Correct 132 ms 19260 KB Output is correct
23 Correct 126 ms 19140 KB Output is correct
24 Correct 137 ms 20192 KB Output is correct
25 Correct 143 ms 24404 KB Output is correct
26 Correct 147 ms 24276 KB Output is correct
27 Correct 140 ms 23992 KB Output is correct
28 Correct 111 ms 18948 KB Output is correct
29 Correct 143 ms 23920 KB Output is correct
30 Correct 63 ms 21572 KB Output is correct
31 Correct 86 ms 27572 KB Output is correct
32 Correct 126 ms 19140 KB Output is correct
33 Correct 156 ms 22172 KB Output is correct
34 Correct 207 ms 23972 KB Output is correct
35 Correct 225 ms 23876 KB Output is correct