oj.uz

Submission #825434

# Submission time Handle Problem Language Result Execution time Memory
825434 2023-08-14T20:12:17 Z NK_ Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 111 ms 32588 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;

	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);
	// cerr << R << endl;

	// assert(false);

	int leaf = L[R]; 
	// cerr << ex << endl;

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

		// cerr << "ENTER" << endl;

		set<int> seen; vi S;
		for(auto x : D) {
			if (st[x] == en[x]) {
				if (seen.count(x)) S.pb(x);
				else seen.insert(x);
			} else {
				S.pb(x);
				F[x]++;
				// cerr << "ADD: " << x << endl;
			}
		}

		if ((leaf + sz(S)) & 1) {
			for(auto& x : S) F[x] = 0;
			cout << -1 << 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++) S.pb(lca(S[x], S[x+1]));

		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++) {
			// cerr << "AT: " << S[u] << endl;
			while(stk.back() != -1 && en[stk.back()] <= st[S[u]]) stk.pop_back();
			
			// parent is stk.back()
			int p = stk.back();
			if (p != -1) chd[p].pb(u);
			else rt = u;
			// cerr << S[u] << " " << (p == -1 ? -1 : S[p]) << endl;
			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]];
			}

			// cerr << S[u] << " " << F[S[u]] << endl;

			if (~(F[S[u]] + L[S[u]]) & 1) {
				// assert(p != -1);
				// cerr << C[0][S[u]] << ", " << C[1][S[u]] << endl;
				// cerr << C[0][S[p]] << ", " << C[1][S[p]] << endl;

				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;
		
		// cerr << "EXIT" << endl;

		cout << (N + K) - 1 + ans - 1 << nl;
	}


    return 0;
}

Compilation message

cleaning.cpp: In lambda function:
cleaning.cpp:153:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  153 |     if (p != -1) ans -= C[1][S[p]]; ans += C[0][S[p]];
      |     ^~
cleaning.cpp:153:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  153 |     if (p != -1) ans -= C[1][S[p]]; ans += C[0][S[p]];
      |                                     ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3664 KB Output is correct
2 Correct 8 ms 3152 KB Output is correct
3 Correct 60 ms 30664 KB Output is correct
4 Correct 89 ms 32588 KB Output is correct
5 Correct 52 ms 27676 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 14892 KB Output is correct
2 Incorrect 83 ms 15124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 30.0

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