oj.uz

Submission #1055372

# Submission time Handle Problem Language Result Execution time Memory
1055372 2024-08-12T18:24:13 Z TAhmed33 Spring cleaning (CEOI20_cleaning) C++
28 / 100
 283 ms 16716 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
const int MAXN = 2e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree {
	int tree[MAXN << 2], lazy[MAXN << 2];
	void prop (int l, int r, int node) {
		if (l != r) {
			lazy[tl] ^= lazy[node];
			lazy[tr] ^= lazy[node];
		}
		if (lazy[node]) {
			tree[node] = r - l + 1 - tree[node];
		}
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] ^= 1;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
		tree[node] = tree[tl] + tree[tr];
	}
	int get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];
		return get(l, mid, a, b, tl) + get(mid + 1, r, a, b, tr);
	}
} cur;
int n, q;
vector <int> adj[MAXN];
int sze[MAXN], nxt[MAXN], dep[MAXN], in[MAXN], out[MAXN], tt;
int p[MAXN];
void fix (int pos, int par) {
	p[pos] = par;
	sze[pos] = 1;
	if (par != 0) {
		adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), par));
	}
	for (auto &j : adj[pos]) {
		fix(j, pos);
		sze[pos] += sze[j];
		if (sze[j] > sze[adj[pos][0]]) {
			swap(j, adj[pos][0]);
		}
	}
}
int leaf[MAXN];
void dfs (int pos) {
	in[pos] = ++tt;
	if (adj[pos].empty()) {
		leaf[pos] = 1;
	}
	for (auto j : adj[pos]) {
		dep[j] = 1 + dep[pos];
		nxt[j] = (j == adj[pos][0] ? nxt[pos] : j);
		dfs(j);
		leaf[pos] += leaf[j];
	}
	out[pos] = tt;
}
void upd (int x) {
	while (x) {
		cur.update(1, n, in[nxt[x]], in[x], 1);
		x = p[nxt[x]];
	}
}
void solve () {
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int root = -1;
	for (int i = 1; i <= n; i++) {
		if (adj[i].size() >= 2) {
			root = i;
			break;
		}
	}
	fix(root, 0);
	nxt[root] = root;
	dfs(root);
	for (int i = 1; i <= n; i++) {
		if (leaf[i] & 1) {
			cur.update(1, n, in[i], in[i], 1);
		}
	}
	while (q--) {
		int d; cin >> d;
		vector <int> c(d);
		for (auto &i : c) {
			cin >> i;
		}
		for (auto i : c) {
			if (leaf[i] == 1) {
				leaf[i]--;
				upd(i);
			}
			upd(i);
		}
		int z = cur.get(1, n, in[root], in[root], 1);
		if (z == 1) {
			cout << -1 << '\n';
		} else {
			int cnt = d;
			cnt += cur.get(1, n, 1, n, 1);
			cnt += 2 * (n - 1 - cur.get(1, n, 1, n, 1));
			cout << cnt << '\n';
		}
		for (auto i : c) {
			if (leaf[i] == 0) {
				leaf[i]++;
				upd(i);
			}
			upd(i);
		}
	}
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Incorrect 139 ms 11748 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 29 ms 11096 KB Output is correct
2 Correct 30 ms 11100 KB Output is correct
3 Correct 31 ms 16080 KB Output is correct
4 Correct 90 ms 15316 KB Output is correct
5 Correct 99 ms 16328 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 12416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 14172 KB Output is correct
2 Correct 283 ms 14932 KB Output is correct
3 Correct 221 ms 13032 KB Output is correct
4 Correct 265 ms 14932 KB Output is correct
5 Correct 273 ms 14928 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 16716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Incorrect 139 ms 11748 KB Output isn't correct
3 Halted 0 ms 0 KB -