oj.uz

Submission #594062

# Submission time Handle Problem Language Result Execution time Memory
594062 2022-07-12T04:01:54 Z penguinhacker Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 18116 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()) {
		//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
			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: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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 228 ms 4124 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3748 KB Output is correct
2 Correct 10 ms 3156 KB Output is correct
3 Correct 30 ms 8976 KB Output is correct
4 Correct 58 ms 8360 KB Output is correct
5 Correct 84 ms 9572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4428 KB Output is correct
2 Correct 11 ms 3804 KB Output is correct
3 Correct 49 ms 18116 KB Output is correct
4 Correct 152 ms 17700 KB Output is correct
5 Correct 44 ms 16892 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 4820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6732 KB Output is correct
2 Correct 179 ms 6648 KB Output is correct
3 Correct 146 ms 5712 KB Output is correct
4 Correct 177 ms 8056 KB Output is correct
5 Correct 189 ms 8012 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 9736 KB Output is correct
2 Correct 67 ms 12548 KB Output is correct
3 Execution timed out 1091 ms 12280 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 228 ms 4124 KB Output is correct
3 Correct 46 ms 3748 KB Output is correct
4 Correct 10 ms 3156 KB Output is correct
5 Correct 30 ms 8976 KB Output is correct
6 Correct 58 ms 8360 KB Output is correct
7 Correct 84 ms 9572 KB Output is correct
8 Correct 84 ms 4428 KB Output is correct
9 Correct 11 ms 3804 KB Output is correct
10 Correct 49 ms 18116 KB Output is correct
11 Correct 152 ms 17700 KB Output is correct
12 Correct 44 ms 16892 KB Output is correct
13 Execution timed out 1047 ms 4820 KB Time limit exceeded
14 Halted 0 ms 0 KB -