Submission #578098

#	Time	Username	Problem	Language	Result	Execution time	Memory
578098		amunduzbaev	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1093 ms	15500 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], nw[N], res;
int is[N];

void dfs(int u, int p = -1){
	sub[u] = nw[u] + is[u];
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		sub[u] += sub[x];
	}
	//~ cout<<u<<" "<<sub[u]<<"\n";
	if(!(sub[u] & 1)){
		//~ cout<<u<<"\n";
		res++;
	}
}

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 cnt = 0;
	for(int i=1;i<=n;i++){
		is[i] = ((int)edges[i].size() == 1);
		cnt += is[i];
	}
	
	for(int i=0;i<q;i++){
		int d; cin>>d;
		vector<int> t, tmp;
		for(int x=0;x<d;x++){
			int p; cin>>p;
			nw[p]++;
			t.push_back(p);
			if(is[p]){
				is[p]--;
				cnt--;
			}
		}
		res = 0, dfs(1);
		if((cnt + d) & 1){
			cout<<-1<<"\n";
		} else {
			cout<<n - 1 + d + res - 1<<"\n";
		}
		for(auto p : t){
			nw[p]--;
			if((int)edges[p].size() == 1 && !is[p]){
				is[p] = 1;
				cnt++;
			}
		}
	}
}

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