Submission #1159336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159336		mendeke	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1095 ms	15636 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 = 100001;

using namespace std;

ll n, q, m, a, b, c, d[N], cntleaves, p[N], used[N], cnt[N], ans, us[N], pr[N], timer;
pair <ll, ll> e[N];
vector <ll> g[N], dr, sf[N], gl[N];
deque <pair <ll, ll>> sol;
deque <ll> st;

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

void ch (ll v, ll pr){
	for (auto i: g[v]){
		if (i != pr){
			ch (i, v);
			d[v] = max (d[v], d[i]);
		}
	}
}

void LT (ll v, ll P, ll dep, ll I){
	d[v] = dep;
	pr[v] = I;
	if (g[v].size() == 1){
		st.pb (dep);
	}
	for (auto i: g[v]){
		if (i != P){
			LT (i, v, dep + 1, I);
		}
	}
}

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;
		a = 0;
		b = 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++;
			}
		}
		d[1] = 1;
		dfs (1, 1);
		a = b = 0;
		for (int i = 1; i <= timer; i++){
			if (a < d[i]){
				a = d[i];
				b = i;
			}
		}
		d[b] = 1;
		dfs (b, b);
		ch (b, b);
		st.pb (b);
		used[b] = 1;
		while (st.size()){
			a = st[0];
			dr.pb (a);
			st.ppf();
			for (auto i: g[a]){
				if (used[i] == 0 && d[i] == d[a]){
					st.pb (i);
					used[i] = 1;
					break;		
				}
			}
		}
		for (auto i: dr){
			d[i] = 0;
			pr[i] = i;
			for (auto j: g[i]){
				st.clear();
				if (used[j] == 0){
					LT (j, i, 1, i);
					for (auto y: st){
						gl[i].pb (y);
					}
				}
			}
		}
		ans += dr.size() - 1;
		sol.clear();
		for (int i = 0; i < dr.size(); i++){
			for (auto j: gl[dr[i]]){
				if (sol.size()){
					ans += sol[0].F + j + (i - sol[0].S);
					sol.ppf(); 
				}
				else{
					sol.pb ({j, i});
				}
			}
		}
		if (cntleaves % 2 == 1){
			cout << "-1\n";
		}
		else{
			cout << ans << '\n';
		}
		ans = 0;
		for (int i = 1; i <= timer; i++){
			g[i].clear();
			gl[i].clear();
			used[i] = 0;
			dr.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