oj.uz

Submission #520252

# Submission time Handle Problem Language Result Execution time Memory
520252 2022-01-29T03:39:54 Z blue Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 1000 ms 26164 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 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';


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

		vi new_leaf = leaf;
		vi new_st_leaf = st_leaf;

		int extra_odd = 0;

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

			int delta = 0;

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

			delta++;
			extra_odd++;

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

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

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

		if(new_st_leaf[rt] % 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] % 2];

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15188 KB Output is correct
2 Execution timed out 1073 ms 16784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15708 KB Output is correct
2 Correct 24 ms 15724 KB Output is correct
3 Correct 59 ms 19952 KB Output is correct
4 Correct 50 ms 19144 KB Output is correct
5 Correct 76 ms 20420 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 16132 KB Output is correct
2 Correct 830 ms 16132 KB Output is correct
3 Correct 639 ms 26164 KB Output is correct
4 Execution timed out 1068 ms 25352 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 17112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 18620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 20692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15188 KB Output is correct
2 Execution timed out 1073 ms 16784 KB Time limit exceeded
3 Halted 0 ms 0 KB -