Submission #1055387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055387		TAhmed33	Spring cleaning (CEOI20_cleaning)	C++98	100 / 100	282 ms	24404 KiB

cleaning

#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 && adj[i].empty()) {
				leaf[i]--;
				upd(i);
			}
			upd(i);
/*		for (int i = 1; i <= n; i++) {
			cout << cur.get(1, n, in[i], in[i], 1) << " ";
		}
		cout << '\n';*/
		}
/*		for (int i = 1; i <= n; i++) {
			cout << cur.get(1, n, in[i], in[i], 1) << " ";
		}
		cout << '\n';*/
		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) {
			upd(i);
			if (leaf[i] == 0 && adj[i].empty()) {
				leaf[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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30