Submission #578131

#	Time	Username	Problem	Language	Result	Execution time	Memory
578131		amunduzbaev	Spring cleaning (CEOI20_cleaning)	C++17	26 / 100	135 ms	23756 KiB

cleaning

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 1e5 + 5;
vector<int> edges[N];
int sub[N], add[N], is[N];
int d[N], par[N][20], pref[N];
int tin[N], tout[N], t, res;

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
	}
	for(auto x : edges[u]){
		if(x == p) continue;
		d[x] = d[u] + 1;
		par[x][0] = u;
		dfs(x, u);
		sub[u] += sub[x];
	}
	
	if(!sub[u]) sub[u] = 1, is[u] = 1;
	tout[u] = t;
}

void dfs2(int u, int p = -1){
	sub[u] &= 1;
	res += (!sub[u]);
	pref[u] += sub[u];
	for(auto x : edges[u]){
		if(x == p) continue;
		pref[x] = pref[u];
		dfs2(x, u);
	}
}

bool isp(int a, int b) { return (tin[a] <= tin[b] && tin[b] <= tout[a]); }
int lca(int a, int b){
	if(isp(a, b)) return a;
	if(isp(b, a)) return b;
	for(int j=19;~j;j--){
		if(!isp(par[a][j], b)) a = par[a][j];
	}
	
	return par[a][0];
}

int solve(vector<int> t){
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	sort(t.begin(), t.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});
	int m = t.size();
	for(int i=1;i<m;i++){
		t.push_back(lca(t[i-1], t[i]));
	}
	
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	sort(t.begin(), t.end(), [&](int a, int b){
		return tin[a] < tin[b];
	});
	
	int tot = 0;
	function<int(int)> dfs = [&](int i){
		int mx = i + 1, u = t[i];
		while(mx < (int)t.size() && tin[t[mx]] < tout[t[i]]){
			int x = t[mx];
			mx = dfs(mx);
			
			if(add[x] & 1){
				tot -= (d[x] - d[u] - pref[x] + pref[u]);
				tot += (pref[x] - pref[u]);
			}
			
			add[u] += add[x];
		}
		
		if(!i && (add[u]&1)){
			tot -= (d[u] - pref[u]);
			tot += pref[u];
		}
		
		return mx;
	};
	dfs(0);
	for(auto x : t) add[x] = 0;
	return tot;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, q; cin>>n>>q;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	int r = -1;
	for(int i=1;i<=n;i++){
		if((int)edges[i].size() > 1) { r = i; break; }
	}
	
	assert(~r);
	
	par[r][0] = d[r] = 1;
	dfs(r);
	dfs2(r);
	//~ cout<<res<<"\n";
	int cnt = accumulate(is + 1, is + n + 1, 0);
	
	for(int i=0;i<q;i++){
		int d; cin>>d;
		//~ cout<<"here"<<endl;
		vector<int> t;
		int tmp = 0;
		for(int x=0;x<d;x++){
			int p; cin>>p;
			//~ nw[p]++;
			t.push_back(p);
			add[p]++, tmp++;
			if(is[p]){
				is[p]--;
				cnt--;
				add[p]--;
			}
		}
		
		if((cnt + d) & 1){
			cout<<-1<<"\n";
		} else {
			
			//~ cout<<n - 1<<" "<<tmp<<" "<<res<<" "<<solve(t)<<"\n";
			cout<<n - 1 + tmp + res + solve(t) - 1<<"\n";
		}
		
		for(auto p : t){
			add[p] = 0;
			if((int)edges[p].size() == 1 && !is[p]){
				is[p] = 1;
				cnt++;
			}
		}
	}
}

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