oj.uz

Submission #825454

# Submission time Handle Problem Language Result Execution time Memory
825454 2023-08-14T20:42:24 Z NK_ Spring cleaning (CEOI20_cleaning) C++17
18 / 100
 190 ms 31372 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using ll = long long;
using vl = V<ll>;

const int LG = 20;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int R = -1; for(int i = 0; i < N; i++) if (sz(adj[i]) > 1) {
		R = i;
		break;
	}

	V<vi> C(2, vi(N)); vi L(N), st(N), en(N); int t = 0; 
	V<vi> up(N, vi(LG)); vi dep(N);

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};

	auto lca = [&](int a, int b) {
		if (dep[a] < dep[b]) swap(a, b);
		a = jmp(a, dep[a] - dep[b]);
		if (a == b) return a;

		for(int i = LG - 1; i >= 0; i--) {
			if (up[a][i] != up[b][i]) {
				a = up[a][i];
				b = up[b][i];
			}
		}

		return up[a][0];
	};

	function<void(int, int)> gen = [&](int u, int p) {
		up[u][0] = p; dep[u] = (u == p ? 0 : dep[p] + 1);
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		st[u] = t++;
		for(auto& v : adj[u]) if (v != p) {
			gen(v, u); L[u] += L[v];
		}
		en[u] = t - 1;

		if (st[u] == en[u]) L[u] = 1;
	};

	gen(R, R);

	int ex = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		C[L[u] & 1][u]++;
		if (L[u] % 2 == 0) ex++;

		for(auto& v : adj[u]) if (v != p) {
			C[0][v] += C[0][u]; 
			C[1][v] += C[1][u]; 
			dfs(v, u); 
		}
	};

	dfs(R, -1);

	int leaves = L[R]; 

	vi F(N, 0), seen(N, 0);
	for(int i = 0; i < Q; i++) {
		int K; cin >> K;
		vi D(K); for(auto& x : D) { cin >> x; --x; }

		vi S;
		for(auto x : D) {
			if (st[x] == en[x]) {
				if (seen[x]) { S.pb(x); F[x]++; }
				else seen[x] = 1;
			} else {
				S.pb(x);
				F[x]++;
			}
		}

		if ((leaves + sz(S)) & 1) {
			for(auto& x : S) F[x] = 0;
			for(auto& x : D) seen[x] = 0;

			cout << -1 << nl;
			continue;
		}

		if (sz(S) == 0) {
			for(auto& x : S) F[x] = 0;
			for(auto& x : D) seen[x] = 0;

			cout << (N + K) - 1 + ex << nl;
			continue;
		}
			
		int ans = ex;
		sort(begin(S), end(S), [&](int x, int y) { return st[x] < st[y]; });

		int M = sz(S);
		for(int x = 0; x < M - 1; x++) {
			int l = lca(S[x], S[x + 1]); S.pb(l);
		}

		sort(begin(S), end(S), [&](int x, int y) { return st[x] < st[y]; });
		S.erase(unique(begin(S), end(S)), end(S)); 

		M = sz(S);
		vi stk = {-1}; V<vi> chd(M);
		int rt = -1;
		for(int u = 0; u < M; u++) {
			while(stk.back() != -1 && en[S[stk.back()]] < st[S[u]]) stk.pop_back();
			
			int p = stk.back();
			if (p != -1) chd[p].pb(u);
			else rt = u;

			stk.pb(u);
		}

		function<void(int, int)> upd = [&](int u, int p) {
			for(auto& v : chd[u]) {
				upd(v, u); 
				F[S[u]] += F[S[v]];
			}

			if (F[S[u]] & 1) {
				ans -= C[0][S[u]]; ans += C[1][S[u]]; 
				if (p != -1) { ans -= C[1][S[p]]; ans += C[0][S[p]]; }
			}
		};

		if (rt != -1) upd(rt, -1);

		for(auto& x : S) F[x] = 0;
		for(auto& x : D) seen[x] = 0;
		
		cout << (N + K) - 1 + ans - 1 << nl;
	}


    return 0;
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2380 KB Output is correct
2 Correct 6 ms 1872 KB Output is correct
3 Correct 57 ms 21052 KB Output is correct
4 Correct 66 ms 16228 KB Output is correct
5 Correct 73 ms 22464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3276 KB Output is correct
2 Correct 7 ms 2768 KB Output is correct
3 Correct 63 ms 29880 KB Output is correct
4 Correct 87 ms 31372 KB Output is correct
5 Correct 50 ms 26996 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5260 KB Output is correct
2 Correct 18 ms 4456 KB Output is correct
3 Incorrect 10 ms 4348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 13844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21272 KB Output is correct
2 Incorrect 190 ms 24540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -