oj.uz

답안 #520253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520253 2022-01-29T03:45:45 Z blue Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 25412 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;

		vi node_delta(1+N, 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;
			// }

			node_delta[a] += delta;

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

		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_st_leaf[rt] + node_delta[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] + node_delta[i]) % 2];

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

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15180 KB Output is correct
2 Execution timed out 1092 ms 16140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 15308 KB Output is correct
2 Correct 16 ms 15312 KB Output is correct
3 Correct 56 ms 19524 KB Output is correct
4 Correct 45 ms 18228 KB Output is correct
5 Correct 66 ms 19564 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15720 KB Output is correct
2 Correct 16 ms 15692 KB Output is correct
3 Correct 69 ms 25340 KB Output is correct
4 Correct 68 ms 24636 KB Output is correct
5 Correct 66 ms 25412 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 16944 KB Output is correct
2 Correct 233 ms 16416 KB Output is correct
3 Correct 263 ms 16420 KB Output is correct
4 Correct 211 ms 16728 KB Output is correct
5 Correct 264 ms 17096 KB Output is correct
6 Correct 297 ms 17092 KB Output is correct

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 17856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1096 ms 19260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15180 KB Output is correct
2 Execution timed out 1092 ms 16140 KB Time limit exceeded
3 Halted 0 ms 0 KB -