Submission #594061

#	Time	Username	Problem	Language	Result	Execution time	Memory
594061		penguinhacker	Spring cleaning (CEOI20_cleaning)	C++17	18 / 100	1085 ms	19344 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, rt, s[mxN], hd[mxN], p[mxN], tin[mxN], t, st[1<<18];
vector<int> adj[mxN];
bool leaf[mxN], parity[mxN], init[mxN], lz[1<<18], vis[mxN];

void dfs1(int u) {
	if (adj[u].empty()) {
		//cout << u << endl;
		leaf[u]=parity[u]=1;
		return;
	}
	for (int& v : adj[u]) {
		adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
		p[v]=u;
		dfs1(v);
		parity[u]^=parity[v];
		s[u]+=s[v];
		if (s[v]>s[adj[u][0]])
			swap(adj[u][0], v);
	}
}

void dfs2(int u, int h) {
	init[t]=parity[u];
	tin[u]=t++;
	hd[u]=h;
	if (adj[u].size()) {
		dfs2(adj[u][0], h);
		for (int i=1; i<adj[u].size(); ++i)
			dfs2(adj[u][i], adj[u][i]);
	}
}

void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u]=init[l];
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

void psh(int u, int l, int r) {
	if (lz[u]) {
		st[u]=r-l+1-st[u];
		if (l!=r)
			lz[2*u]^=1, lz[2*u+1]^=1;
		lz[u]=0;
	}
}

void upd(int ql, int qr, int u=1, int l=0, int r=n-1) {
	psh(u, l, r);
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		lz[u]=1;
		psh(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	upd(ql, qr, 2*u, l, mid);
	upd(ql, qr, 2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

void upd_node(int u) {
	for (; hd[u]!=rt; u=p[hd[u]])
		upd(tin[hd[u]], tin[u]);
	upd(0, tin[u]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i=0; i<n; ++i)
		if (adj[i].size()>1) {
			rt=i;
			break;
		}
	dfs1(rt);
	dfs2(rt, rt);
	bld();
	while(q--) {
		int k;
		cin >> k;
		vector<int> nodes(k);
		bool leaves=parity[rt];
		for (int& i : nodes) {
			cin >> i, --i;
			if (leaf[i]&&!vis[i]) {
				vis[i]=1;
				leaves^=1;
			}
			leaves^=1;
		}
		if (leaves) { // odd number of leaves bad
			cout << "-1\n";
		} else {
			vector<int> rb;
			for (int i : nodes) {
				if (vis[i]) {
					vis[i]=0;
					continue;
				}
				upd_node(i);
				rb.push_back(i);
			}
			int ans=2*(n-1)-st[1]+nodes.size();
			cout << ans << "\n";
			for (int i : rb)
				upd_node(i);
		}
	}
	return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'void dfs2(int, int)':
cleaning.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=1; i<adj[u].size(); ++i)
      |                 ~^~~~~~~~~~~~~~

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