oj.uz

Submission #349029

# Submission time Handle Problem Language Result Execution time Memory
349029 2021-01-16T11:02:25 Z dolphingarlic Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 182 ms 26080 KB 
#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<int> graph[100001];
int leaves[100001], tot_leaves = 0, bad = 0;
bool is_leaf[100001];
int tin[100001], tout[100001], timer = 0, anc[100001][18];

vector<int> vtree[100001];
int ans, bit[100001];
int a[100001], l_delta[100001];

void update(int pos, int val) { for (; pos <= n; pos += pos & -pos) bit[pos] += val; }

int query(int l, int r) {
	int res = 0;
	for (; r; r -= r & -r) res += bit[r];
	for (l--; l; l -= l & -l) res -= bit[l];
	return res;
}

void lca_dfs(int node, int parent = 0) {
	// LCA stuff
	tin[node] = ++timer;
	for (int i = 1; i < 18; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
	// Check whether it's a leaf
	if (graph[node].size() == 1) {
		leaves[node] = 1;
		tot_leaves++;
		is_leaf[node] = true;
	}
	// DFS on children
	for (int i : graph[node]) if (i != parent) {
		anc[i][0] = node;
		lca_dfs(i, node);
		leaves[node] += leaves[i];
	}
	tout[node] = timer;
	// Set what happens when we toggle the parity
	if (leaves[node] & 1) update(tin[node], 1), update(tout[node] + 1, -1);
	else {
		update(tin[node], -1), update(tout[node] + 1, 1);
		bad++;
	}
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

int lca(int u, int v) {
	if (is_ancestor(u, v)) return u;
	for (int i = 17; ~i; i--) if (anc[u][i] && !is_ancestor(anc[u][i], v)) u = anc[u][i];
	return anc[u][0];
}

void vtree_dfs(int node, int parent = 0) {
	for (int i : vtree[node]) if (i != parent) {
		vtree_dfs(i, node);
		l_delta[node] += l_delta[i];
	}
	ans += (l_delta[node] & 1) * query(tin[parent] + 1, tin[node]);
}

bool cmp(int u, int v) { return tin[u] < tin[v]; }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (graph[i].size() > 1) {
		lca_dfs(i);
		break;
	}

	while (q--) {
		// Read query data and update original tree
		int d;
		cin >> d;
		vector<int> nodes;
		for (int i = 0; i < d; i++) {
			cin >> a[i];
			if (is_leaf[a[i]]) is_leaf[a[i]] = false;
			else {
				leaves[a[i]]++;
				tot_leaves++;
				l_delta[a[i]]++;
				nodes.push_back(a[i]);
			}
		}

		// Construct the virtual tree
		sort(nodes.begin(), nodes.end(), cmp);
		int m = nodes.size();
		for (int i = 1; i < m; i++) nodes.push_back(lca(nodes[i - 1], nodes[i]));
		sort(nodes.begin(), nodes.end(), cmp);
		nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
		
		vector<int> stck;
		for (int i : nodes) {
			while (stck.size() > 1 && !is_ancestor(stck.back(), i)) {
				vtree[stck[stck.size() - 2]].push_back(stck.back());
				stck.pop_back();
			}
			stck.push_back(i);
		}
		while (stck.size() > 1) {
			vtree[stck[stck.size() - 2]].push_back(stck.back());
			stck.pop_back();
		}

		// Compute and output the answer
		if (tot_leaves & 1) cout << "-1\n";
		else {
			ans = n + d + bad - 2;
			if (stck.size()) vtree_dfs(stck[0]);
			cout << ans << '\n';
		}

		// Reset the original tree
		for (int i = 0; i < d; i++) {
			if (leaves[a[i]] == 1) is_leaf[a[i]] = true;
			else {
				leaves[a[i]]--;
				tot_leaves--;
			}
		}

		// Reset the vtree
		for (int i : nodes) {
			vtree[i].clear();
			l_delta[i] = 0;
		}
	}
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 50 ms 7788 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6892 KB Output is correct
2 Correct 37 ms 6892 KB Output is correct
3 Correct 72 ms 17508 KB Output is correct
4 Correct 72 ms 15076 KB Output is correct
5 Correct 109 ms 18660 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7796 KB Output is correct
2 Correct 48 ms 7536 KB Output is correct
3 Correct 74 ms 24904 KB Output is correct
4 Correct 129 ms 26080 KB Output is correct
5 Correct 66 ms 22892 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8600 KB Output is correct
2 Correct 26 ms 7660 KB Output is correct
3 Correct 19 ms 7532 KB Output is correct
4 Correct 17 ms 8172 KB Output is correct
5 Correct 19 ms 8300 KB Output is correct
6 Correct 37 ms 8428 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13420 KB Output is correct
2 Correct 102 ms 13292 KB Output is correct
3 Correct 67 ms 9324 KB Output is correct
4 Correct 109 ms 13548 KB Output is correct
5 Correct 96 ms 13420 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 17900 KB Output is correct
2 Correct 150 ms 20588 KB Output is correct
3 Correct 144 ms 20716 KB Output is correct
4 Correct 147 ms 20032 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 50 ms 7788 KB Output is correct
3 Correct 39 ms 6892 KB Output is correct
4 Correct 37 ms 6892 KB Output is correct
5 Correct 72 ms 17508 KB Output is correct
6 Correct 72 ms 15076 KB Output is correct
7 Correct 109 ms 18660 KB Output is correct
8 Correct 47 ms 7796 KB Output is correct
9 Correct 48 ms 7536 KB Output is correct
10 Correct 74 ms 24904 KB Output is correct
11 Correct 129 ms 26080 KB Output is correct
12 Correct 66 ms 22892 KB Output is correct
13 Correct 55 ms 8600 KB Output is correct
14 Correct 26 ms 7660 KB Output is correct
15 Correct 19 ms 7532 KB Output is correct
16 Correct 17 ms 8172 KB Output is correct
17 Correct 19 ms 8300 KB Output is correct
18 Correct 37 ms 8428 KB Output is correct
19 Correct 79 ms 13420 KB Output is correct
20 Correct 102 ms 13292 KB Output is correct
21 Correct 67 ms 9324 KB Output is correct
22 Correct 109 ms 13548 KB Output is correct
23 Correct 96 ms 13420 KB Output is correct
24 Correct 127 ms 17900 KB Output is correct
25 Correct 150 ms 20588 KB Output is correct
26 Correct 144 ms 20716 KB Output is correct
27 Correct 147 ms 20032 KB Output is correct
28 Correct 120 ms 12780 KB Output is correct
29 Correct 182 ms 21236 KB Output is correct
30 Correct 90 ms 18532 KB Output is correct
31 Correct 134 ms 26068 KB Output is correct
32 Correct 134 ms 13292 KB Output is correct
33 Correct 156 ms 18412 KB Output is correct
34 Correct 179 ms 21612 KB Output is correct
35 Correct 181 ms 21484 KB Output is correct