Submission #1218380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218380		MateiKing80	Spring cleaning (CEOI20_cleaning)	C++20	28 / 100	393 ms	21060 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 1e5 + 5;
vector<int> vec[N];
int root, sz[N], heavyHead[N], tata[N], posHeavy[N], heavy[N], p;
int leavesSubarb[N], isLeaf[N], lastScos[N], n;

void dfs1(int nod, int papa) {
	sz[nod] = 1;
	tata[nod] = papa;
	for (auto i : vec[nod])
		if (i != papa) {
			dfs1(i, nod);
			sz[nod] += sz[i];
			leavesSubarb[nod] += leavesSubarb[i];
		}
	if (leavesSubarb[nod] == 0) {
		leavesSubarb[nod] ++;
		isLeaf[nod] = 1;
	}
}

void dfs2(int nod, int papa) {
	posHeavy[nod] = ++ p;
	heavy[p] = nod;
	sort(vec[nod].begin(), vec[nod].end(), [&](int a, int b) {return sz[a] > sz[b];});
	int hh = 0;
	for (auto i : vec[nod])
		if (i != papa) {
			if (!hh) {
				heavyHead[i] = heavyHead[nod];
				hh = 1;
			} else {
				heavyHead[i] = i;
			}
			dfs2(i, nod);
		}
}

pii aint[4 * N];
int lazy[4 * N];

pii join(pii a, pii b) {
	return {a.fr + b.fr, a.sc + b.sc};
}

void build(int pos, int l, int r) {
	aint[pos] = {0, r - l + 1};
	if (l != r) {
		build (2 * pos, l, (l + r) >> 1);
		build (2 * pos + 1, ((l + r) >> 1) + 1, r);
	}
}

void propag(int pos) {
	if (lazy[pos] == 0)
		return;
	aint[pos].fr = aint[pos].sc - aint[pos].fr;
	if (2 * pos + 1 < 4 * N) {
		lazy[2 * pos] ^= 1;
		lazy[2 * pos + 1] ^= 1;
	}
	lazy[pos] = 0;
}

void update(int pos, int st, int dr, int l, int r) {
	propag(pos);
	if (l <= st && dr <= r) {
		lazy[pos] ^= 1;
		propag(pos);
		return;
	}
	int mid = (st + dr) >> 1;
	
	if (l <= mid)
		update(2 * pos, st, mid, l, r);
	else
		propag(2 * pos);
	
	if (mid < r)
		update(2 * pos + 1, mid + 1, dr, l, r);
	else
		propag(2 * pos + 1);
	
	aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

pii query(int pos, int st, int dr, int l, int r) {
	propag(pos);
	if (l <= st && dr <= r)
		return aint[pos];
	
	int mid = (st + dr) >> 1;
	if (r <= mid)
		return query(2 * pos, st, mid, l, r);
	if (mid < l)
		return query(2 * pos + 1, mid + 1, dr, l, r);
	return join(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
}

void updateUp(int nod) {
	if (nod == 0)
		return;
	update(1, 1, n, posHeavy[heavyHead[nod]], posHeavy[nod]);
	updateUp(tata[heavyHead[nod]]);
}

int main() {
	int q;
	cin >> n >> q;
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	int leaves = 0;
	for (int i = 1; i <= n; i ++) {
		if (vec[i].size() > 1)
			root = i;
		else
			leaves ++;
	}
	dfs1(root, 0);
	heavyHead[root] = root;
	dfs2(root, 0);
	build(1, 1, n);
	for (int i = 1; i <= n; i ++)
		if (leavesSubarb[heavy[i]] % 2 == 0)
			update(1, 1, n, i, i);
	for (int id = 1; id <= q; id ++) {
		int d;
		cin >> d;
		vector<int> a;
		int newLeaves = 0;
		for (int i = 0; i < d; i ++) {
			int x;
			cin >> x;
			a.push_back(x);
			updateUp(x);
			newLeaves ++;
			if (isLeaf[x] && lastScos[x] < id) {
				lastScos[x] = id;
				updateUp(x);
				newLeaves --;
			}
		}
		if (newLeaves % 2 == 0)
			cout << n - 1 + d + query(1, 1, n, 2, n).fr << '\n';
		else
			cout << "-1\n";
		for (auto x : a) {
			updateUp(x);
			if (isLeaf[x] && lastScos[x] == id) {
				lastScos[x] = 0;
				updateUp(x);
			}
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30