제출 #520278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520278		blue	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	225 ms	27572 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 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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30