oj.uz

Submission #938608

# Submission time Handle Problem Language Result Execution time Memory
938608 2024-03-05T11:09:33 Z Halym2007 Spring cleaning (CEOI20_cleaning) C++11
70 / 100
 265 ms 27048 KB 
// 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Incorrect 13 ms 12376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16396 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Correct 20 ms 17352 KB Output is correct
4 Correct 31 ms 19144 KB Output is correct
5 Correct 37 ms 20424 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16728 KB Output is correct
2 Correct 19 ms 16720 KB Output is correct
3 Correct 30 ms 24916 KB Output is correct
4 Correct 80 ms 27048 KB Output is correct
5 Correct 27 ms 23800 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 15184 KB Output is correct
2 Correct 150 ms 13916 KB Output is correct
3 Correct 232 ms 13784 KB Output is correct
4 Correct 256 ms 14380 KB Output is correct
5 Correct 218 ms 14516 KB Output is correct
6 Correct 265 ms 14684 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14988 KB Output is correct
2 Correct 59 ms 15148 KB Output is correct
3 Correct 47 ms 13212 KB Output is correct
4 Correct 57 ms 14976 KB Output is correct
5 Correct 50 ms 14964 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17192 KB Output is correct
2 Correct 69 ms 19680 KB Output is correct
3 Correct 82 ms 19928 KB Output is correct
4 Correct 65 ms 19216 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Incorrect 13 ms 12376 KB Output isn't correct
3 Halted 0 ms 0 KB -