Submission #1159381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159381		mendeke	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1096 ms	13600 KiB

cleaning

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 300001;

using namespace std;

ll n, q, m, a, b, c, d[N], cntleaves, p[N], sz[N], timer, cen, ans;
vector <ll> g[N], v;
pair <ll, ll> e[N];

void pre_calc (ll v, ll pr){
	sz[v] = 1;
	for (auto i: g[v]){
		if (i != pr){
			pre_calc (i, v);
			sz[v] += sz[i];
		}
	}
}

ll find_c (ll v, ll pr){
	for (auto i: g[v]){
		if (i != pr && sz[i] > n / 2){
			return find_c (i, v);
		}
	}
	return v;
}

void dfs (ll v, ll pr, ll dep){
	if (g[v].size() == 1){
		ans += dep;
	}
	for (auto i: g[v]){
		if (i != pr){
			dfs (i, v, dep + 1);
		}
	}
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i < n; i++){
		cin >> e[i].F >> e[i].S;
		a = e[i].F, b = e[i].S;
		g[a].pb (b);
		g[b].pb (a);
	}
	for (int z = 1; z <= q; z++){
		cin >> m;
		ans = 0;
		timer = n;
		for (int j = 1; j <= m; j++){
			cin >> p[j];
			++timer;
			g[p[j]].pb (timer);
			g[timer].pb (p[j]);
		}
		cntleaves = 0;
		for (int i = 1; i <= timer; i++){
			if (g[i].size() == 1){
				cntleaves++;
			}
		}
		pre_calc (1, 1);
		cen = find_c (1, 1);
//		cout << cen << ' ';
		for (auto i: g[cen]){
			dfs (i, cen, 1);
		}
//		cout << '\n';
		if (cntleaves % 2){
			ans = -1;
		}
		cout << ans << '\n';
		for (int i = 1; i <= timer; i++){
			g[i].clear();
		}
		for (int i = 1; i < n; i++){
			a = e[i].F, b = e[i].S;
			g[a].pb (b);
			g[b].pb (a);
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30