Submission #602753

#	Time	Username	Problem	Language	Result	Execution time	Memory
602753		vanic	Spring cleaning (CEOI20_cleaning)	C++14	34 / 100	1090 ms	18624 KiB

cleaning

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
vector < int > novi;

int sol;
int root;

int dfs(int x, int prosl){
	int br=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			br+=dfs(ms[x][i], x);
		}
	}
	if(x==prosl){
		if(br&1){
			return -1;
		}
		return 0;
	}
	if(!br){
		br++;
	}
	if(br&1){
		sol++;
	}
	else{
		sol+=2;
	}
	return br;
}

void rijesi(){
	sol=0;
	if(dfs(root, root)==-1){
		cout << -1 << '\n';
		return;
	}
	cout << sol << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	int a, b;
	for(int i=0; i<n-1; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	for(int i=0; i<n; i++){
		if(ms[i].size()>1){
			root=i;
			break;
		}
	}
	int m;
	for(int i=0; i<q; i++){
		cin >> m;
		for(int j=0; j<m; j++){
			cin >> a;
			a--;
			ms[a].push_back(j+n);
			ms[j+n].push_back(a);
			novi.push_back(a);
			novi.push_back(j+n);
		}
		rijesi();
		for(int j=0; j<m*2; j++){
			ms[novi[j]].pop_back();
		}
		novi.clear();
	}
	return 0;
}

• 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