oj.uz

Submission #912748

# Submission time Handle Problem Language Result Execution time Memory
912748 2024-01-19T20:05:42 Z NK_ The Xana coup (BOI21_xanadu) C++17
10 / 100
 79 ms 39760 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 sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	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);
	}	

	vi on(N); for(auto& x : on) cin >> x;

	V<V<vi>> dp(N, V<vi>(2, vi(2, INF)));

	function<void(int, int)> dfs = [&](int u, int p) {
		int amt = 0;
		for(auto& v : adj[u]) if (v != p) { dfs(v, u); amt++; }

		if (amt == 0) {
			// cout << u << " => " << on[u] << endl;
			dp[u][on[u]][0] = 0;
			dp[u][on[u] ^ 1][1] = 1;
		} else {
			for(int f = 0; f < 2; f++) {
				int took = 0, flip = 0; vi chd;
				for(auto& v : adj[u]) if (v != p) {
					took += dp[v][f][1]; flip ^= 1;
					chd.pb(dp[v][f][0] - dp[v][f][1]);
				}

				sort(begin(chd), end(chd));

				dp[u][on[u] ^ f ^ flip][f] = min(dp[u][on[u] ^ f ^ flip][f], took + f);
				for(int i = 0; i < sz(chd); i++) {
					took += chd[i]; flip ^= 1;
					dp[u][on[u] ^ f ^ flip][f] = min(dp[u][on[u] ^ f ^ flip][f], took + f);
				}
			}
		}

		// cout << u << endl;
		// for(int v = 0; v < 2; v++) for(int f = 0; f < 2; f++) {
		// 	cout << v << " " << f << " ====> " << dp[u][v][f] << endl;
		// }

	};

	dfs(0, -1);

	int ans = min(dp[0][0][0], dp[0][0][1]);
	if (ans == INF) cout << "impossible" << nl;
	else cout << ans << nl;

	exit(0-0);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 39504 KB Output is correct
2 Correct 64 ms 38992 KB Output is correct
3 Correct 65 ms 39708 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 39504 KB Output is correct
2 Correct 64 ms 38992 KB Output is correct
3 Correct 68 ms 39760 KB Output is correct
4 Incorrect 79 ms 20184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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