Submission #938608

#	Time	Username	Problem	Language	Result	Execution time	Memory
938608		Halym2007	Spring cleaning (CEOI20_cleaning)	C++11	70 / 100	265 ms	27048 KiB

cleaning

// problem B
#include <bits/stdc++.h>
using namespace std;
#define sz size()
#define pb push_back
#define ff first
#define ss second
const int N = 2e5 + 5;
int n, q, l[N], r[N], par[N], d, sub[N], sum, rt, a[N], leaf[N], leaf1[N], sub1[N];
map <int, int> m;
pair <int, int> val[N];
vector <int> v[N];
void dfs (int x, int pr) {
	par[x] = pr;
	for(int i : v[x]){
		if(i == pr) continue;
		dfs(i, x);
		sub[x] += sub[i];
	}
	if((int)v[x].sz == 1) {
		sub[x]++;
		leaf[x] = 1;
	}
	if(~pr) {
		sum += (sub[x] % 2 ? 1 : 2);
	}
} 

void dfs1 (int x, int pr, int bir, int iki) {
	for (int i : v[x]) {
		if (i == pr) continue;
		int new_bir = bir, new_iki = iki;
		if (sub[i] % 2) new_bir++;
		else new_iki++;
		val[i] = {new_bir, new_iki};
		dfs1 (i, x, new_bir, new_iki);
	}
} 

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i < n; ++i) {
		cin >> l[i] >> r[i];
	}
	if ((q == 1) or (n <= 20000 and q <= 300)) {
		while ( q-- ) {
			for (int i = 1; i < n; ++i) {
				v[l[i]].pb (r[i]);
				v[r[i]].pb (l[i]);
			}
			for(int i = 1; i <= n; ++i){
				if((int)v[i].sz > 1){
					rt = i;
					break;
				}
			}
			cin >> d;
			for (int i = 1; i <= d; ++i) {
				cin >> a[i];
			}
			int san = n;
			for (int i = 1; i <= d; ++i) {
				san++;
				v[a[i]].pb (san);
				v[san].pb (a[i]);
			}
			sum = 0;
			for (int i = 1; i <= san; ++i) sub[i] = 0;
			dfs (rt, -1);
			cout << (sub[rt] % 2 ? -1 : sum) << '\n';
			for (int i = 1; i <= san; ++i) {
				v[i].clear();
			}
		}
		return 0;
	}
	for (int i = 1; i < n; ++i) {
		v[l[i]].pb (r[i]);
		v[r[i]].pb (l[i]);
	}
	for(int i = 1; i <= n; ++i){
		if((int)v[i].sz > 1){
			rt = i;
			break;
		}
	}
	bool subtask5 = 0;
	for (int i = 1; i <= n; ++i) {
		if (i == rt and (int)v[i].sz != 2) {
			subtask5 = 1;
			break;
		}
		else if (i != rt) {
			if ((int)v[i].sz > 3 or (int)v[i].sz % 2 == 0) {
				subtask5 = 1;
				break;
			}
		}
	}
	if (!subtask5) {
		dfs (rt, -1);
		while ( q-- ) {
			cin >> d;
			m.clear();
			int va = 0;
			for (int i = 1; i <= d; ++i) {
				cin >> a[i];
				m[a[i]]++;
			}
			for (auto i : m) {
				if (leaf[i.ff]) {
					va += i.ss - 1;
				}
				else {
					va += i.ss;
				}
			}
			if (va % 2) {
				cout << "-1\n";
				continue;
			}
			for (int i = 1; i <= d; ++i) {
				int x = a[i];
				while (x != -1) {
					sub1[x] = sub[x];
					leaf1[x] = leaf[x];
					x = par[x];
				}
				if (leaf[a[i]]) {
					sub1[a[i]] = 0;
				}
			}
			int sum1 = sum;
			for (int i = 1; i <= d; ++i) {
				int x = a[i];
				sum1++; 
				if(!leaf1[x]) {
					while (x != rt) {
						if (sub1[x] % 2) {
							sum1++;
							sub1[x] = 2;
						}
						else {
							sum1--;
							sub1[x] = 1;
						}
						x = par[x];
					}
				}
				else {
					leaf1[x] = 0;
					sub1[x] = 1;
				}
			}
			cout << sum1 << "\n";
		}
	}
	else {
		dfs (rt, -1);
		dfs1 (rt, -1, 0, 0);
		while ( q-- ) {
			cin >> d;
			for (int i = 1; i <= d; ++i) {
				cin >> a[i];
			}
			if (!(sub[rt] % 2)) {
				if (leaf[a[1]]) {
					cout << sum + 1 << "\n";
				}
				else {
					cout << "-1" << "\n";
				}
			}
			else {
				// sum = -1
				if (leaf[a[1]]) {
					cout << "-1" << "\n";
				}
				else {
					int jog = sum - val[a[1]].ff - (2 * val[a[1]].ss);
					int jog1 = (val[a[1]].ff * 2) + val[a[1]].ss + 1;
					cout << jog + jog1 << "\n";
				}
			}
		}
	}
} 

• 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: 0 / 30