oj.uz

Submission #594099

# Submission time Handle Problem Language Result Execution time Memory
594099 2022-07-12T05:37:42 Z penguinhacker Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 187 ms 18424 KB 
#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()) {
		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) {
	int ops=1;
	for (; hd[u]!=rt; u=p[hd[u]])
		upd(tin[hd[u]], tin[u]), ++ops;
	upd(0, tin[u]);
	assert(ops<19);
}

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
			for (int i : nodes)
				vis[i]=0;
			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

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 12 ms 8404 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4172 KB Output is correct
2 Correct 9 ms 3600 KB Output is correct
3 Correct 39 ms 9328 KB Output is correct
4 Correct 64 ms 8520 KB Output is correct
5 Correct 69 ms 9912 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4812 KB Output is correct
2 Correct 9 ms 4180 KB Output is correct
3 Correct 50 ms 18424 KB Output is correct
4 Correct 172 ms 18208 KB Output is correct
5 Correct 45 ms 17128 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 10164 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7116 KB Output is correct
2 Correct 185 ms 7092 KB Output is correct
3 Correct 186 ms 5664 KB Output is correct
4 Correct 186 ms 8144 KB Output is correct
5 Correct 187 ms 7992 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 18152 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 12 ms 8404 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -