oj.uz

Submission #720916

# Submission time Handle Problem Language Result Execution time Memory
720916 2023-04-09T18:54:46 Z Szil Spring cleaning (CEOI20_cleaning) C++14
0 / 100
 1000 ms 9424 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

struct Node {
	int s = 0;
	int cnt = 0;
};

vector<int> g[MAXN];
int depth[MAXN], parent[MAXN], pos[MAXN], head[MAXN], heavy[MAXN], timer = 0, n, q, leaf[MAXN];
Node tree[2 * MAXN];

void build(int u) {
	while (u > 1) {
		u /= 2;
		tree[u].s = tree[2*u].s + tree[2*u+1].s;
	}
}

void build() {
	for (int i = 2 * n; i > n; i--) {
		tree[i].cnt = 1;
	}
	for (int i = n; i >= 1; i--) {
		tree[i].cnt = tree[2*i].cnt + tree[2*i+1].cnt;
	}
}

void apply(int u) {
	tree[u].s = (tree[u].cnt - tree[u].s);
}

int dfs(int u, int d) {
	depth[u] = d;
	int s = 1, max_s = 0;
	for (int v : g[u])  {
		if (v != parent[u]) {
			parent[v] = u;
			int k = dfs(v, d + 1);
			s += k;
			if (k > max_s) {
				max_s = k;
				heavy[u] = v;
			}
		}
	}
	return s;
}

void decomp(int u, int h) {
	head[u] = h;
	pos[u] = ++timer;
	if (heavy[u])
		decomp(heavy[u], h);
	for (int v : g[u]) {
		if (v != parent[u] && v != heavy[u])
			decomp(v, v);
	}
}

int qry() {
	return tree[1].cnt-tree[1].s;
}

void segupd(int l, int r) {
	l += n; r += n;
	int a = l, b = r;
	while (l <= r) {
		if (l % 2 == 1) apply(l++);
		if (r % 2 == 0) apply(r--);
		l /= 2; r /= 2;
	}
	for (int i = 1; i <= n; i++) build(i+n);
	build(a);
	build(b);
}

void upd(int a, int b) {

	for (; head[a] != head[b]; b = parent[head[b]]) {
		if (depth[head[a]] > depth[head[b]])
			swap(a, b);
		segupd(pos[head[b]], pos[b]);
	}
	if (depth[a] > depth[b])
		swap(a, b);
	segupd(pos[a], pos[b]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	dfs(1, 0);
	decomp(1, 1);
	build();

	int leaves = 0;

	for (int i = 1; i <= n; i++) {
		leaf[i] = g[i].size() == 1;
		if (leaf[i]) {
			upd(1, i);
			leaves++;
		}
	}

	while (q--) {
		int c; cin >> c;
		vector<int> v(c);
		for (int i = 0; i < c; i++) {
			cin >> v[i];

			if (leaf[v[i]] == 1) {
				leaf[v[i]] = 2;
			} else {
				upd(1, v[i]);
				leaves++;
			}
		}
		if (leaves % 2 == 1) {
			cout << "-1\n";
		} else {
			cout << n - 2 + c + qry() << "\n";
		}

		for (int i = 0; i < c; i++) {

			if (leaf[v[i]] == 2) {
				leaf[v[i]] = 1;
			} else {
				upd(1, v[i]);
				leaves--;
			}
		}

	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Execution timed out 1088 ms 4060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 3168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 3668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 4760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 6976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 9424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Execution timed out 1088 ms 4060 KB Time limit exceeded
3 Halted 0 ms 0 KB -