oj.uz

Submission #594061

# Submission time Handle Problem Language Result Execution time Memory
594061 2022-07-12T03:59:51 Z penguinhacker Spring cleaning (CEOI20_cleaning) C++17
18 / 100
 1000 ms 19344 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
			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 2 ms 2644 KB Output is correct
2 Incorrect 185 ms 4736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4224 KB Output is correct
2 Correct 9 ms 3540 KB Output is correct
3 Correct 29 ms 9660 KB Output is correct
4 Correct 65 ms 9236 KB Output is correct
5 Correct 61 ms 10852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4872 KB Output is correct
2 Correct 9 ms 4180 KB Output is correct
3 Correct 48 ms 19280 KB Output is correct
4 Correct 174 ms 19344 KB Output is correct
5 Correct 45 ms 17780 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8012 KB Output is correct
2 Incorrect 150 ms 8104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 11444 KB Output is correct
2 Correct 70 ms 14548 KB Output is correct
3 Execution timed out 1073 ms 13560 KB Time limit exceeded
4 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 Incorrect 185 ms 4736 KB Output isn't correct
3 Halted 0 ms 0 KB -