oj.uz

Submission #520268

# Submission time Handle Problem Language Result Execution time Memory
520268 2022-01-29T04:37:57 Z blue Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 25376 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];





	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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Execution timed out 1091 ms 16396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15564 KB Output is correct
2 Correct 17 ms 15560 KB Output is correct
3 Correct 58 ms 19596 KB Output is correct
4 Correct 47 ms 18620 KB Output is correct
5 Correct 67 ms 19928 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15948 KB Output is correct
2 Correct 18 ms 15960 KB Output is correct
3 Correct 61 ms 25376 KB Output is correct
4 Correct 64 ms 24728 KB Output is correct
5 Correct 57 ms 24392 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 16744 KB Output is correct
2 Correct 195 ms 16056 KB Output is correct
3 Correct 245 ms 16068 KB Output is correct
4 Correct 196 ms 17040 KB Output is correct
5 Correct 234 ms 16608 KB Output is correct
6 Correct 265 ms 16564 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 18104 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 1092 ms 19392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Execution timed out 1091 ms 16396 KB Time limit exceeded
3 Halted 0 ms 0 KB -