Submission #908777

#	Time	Username	Problem	Language	Result	Execution time	Memory
908777		Nonoze	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	353 ms	47436 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)(x.size())
const int LOG=25;

int n, q;
vector<vector<int>> adj;
vector<int> depth;
vector<vector<int>> up;
vector<vector<int>> graph;
map<int, int> mp;
vector<int> prefix;
vector<int> parity;
vector<pair<int, int>> isin;
int cntleaf=0, tot=0;
int ans=0;
int begining=0;

bool sortt(int a, int b) {return isin[a].first<isin[b].first;}

void dfsdepth(int s, int lst, int &act) {
	isin[s].first=act++;
	if (adj[s].size()==1) prefix[s]++;
	for (auto u: adj[s]) {
		if (u==lst) continue;
		depth[u]=depth[s]+1;
		up[u][0]=s;
		for (int i=1; i<LOG; i++) {
			up[u][i]=up[ up[u][i-1] ][i-1];
		}
		dfsdepth(u, s, act);
		prefix[s]+=prefix[u];
	}
	isin[s].second=act++;
	return;
}

void dfsparity(int s, int lst=-1) {
	for (auto u: adj[s]) {
		if (u==lst) continue;
		parity[u]=parity[s]+(prefix[u]+1)%2;
		dfsparity(u, s);
	}
	if (lst==-1) tot+=n-1;
	else tot+=(prefix[s]+1)%2;
	return;
}

int dfstot(int s, int lst) {
	int comp=mp[s];
	for (auto u: graph[s]) {
		comp+=dfstot(u, s);
	}
	//if (sz(adj[s])<2) comp++;
	if (comp%2==1) {
		int temp=parity[s], d=depth[s];
		if (lst>=0) temp-=parity[lst], d-=depth[lst];
		ans-=temp;
		ans+=d-temp;
	}
	//if (sz(adj[s])<2) comp--;
	return comp;
}

int lca(int a, int b) {
	if (depth[a]<depth[b]) swap(a, b);
	for (int i=LOG-1; i>=0; i--) {
		if (depth[a]-depth[b] >= (1<<i)) {
			a=up[a][i];
		}
	}
	if (a==b) return a;
	for (int i=LOG-1; i>=0; i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}


int ALLPROBLEM() {
	int lst=cntleaf;
	while(q--) {
		cntleaf=lst;
		int d; cin >> d;
		mp.clear();
		for (int i=0; i<d; i++) {
			int u; cin >> u, u--;
			if (sz(adj[u])>1 || mp[u]) {
				cntleaf++;
			} else mp[u]++;
			mp[u]++;
		}
		if (cntleaf%2==1) {
			cout << -1 << endl;
			continue;
		}
		vector<int> change;
		for (auto u: mp) {
			if (u.second&1) change.push_back(u.first);
		}
		sort(change.begin(), change.end(), sortt);
		set<int> L;
		for (int i=0; i< sz(change); i++) {
		    L.insert(change[i]);
			if (i!=0) L.insert(lca(change[i], change[i-1]));
		}
		vector<int> vec;
		for (auto u=L.begin(); u!=L.end(); u++) {
			vec.push_back(*u);
		}
		sort(vec.begin(), vec.end(), sortt);
		stack<int> act;
		if (!vec.empty() && vec[0]!=begining) act.push(begining);
		for (auto u: vec) {
			while (!act.empty() && isin[act.top()].second<isin[u].first) act.pop();
			if (!act.empty() && act.top()!=u) graph[act.top()].push_back(u);
			act.push(u);
		}
		ans=tot+d;
		if (!vec.empty()) dfstot(vec[0], begining);
		cout << ans << endl;
		for (auto u: vec) graph[u].clear();
		graph[begining].clear();
	}
	return 0;
}

int solve() {
	cin >> n >> q;
	adj.resize(n);
	graph.resize(n);
	up.resize(n, vector<int> (LOG, 0));
	depth.resize(n, 0);
	prefix.resize(n, 0);
	parity.resize(n, 0);
	isin.resize(n);
	for (int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (auto u: adj) if (sz(u)==1) cntleaf++;
	int temp=0;
	begining=0;
	dfsdepth(begining, -1, temp);

	dfsparity(begining);
	return ALLPROBLEM();
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

• 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