Submission #522868

#	Time	Username	Problem	Language	Result	Execution time	Memory
522868		Vladithur	The Xana coup (BOI21_xanadu)	C++17	100 / 100	80 ms	19372 KiB

xanadu

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define RINIT mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;

struct chash {
    static inline uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    inline size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
 
    inline size_t operator()(const pair<uint64_t, uint64_t> &v) const {
        chash int_hasher;
        return int_hasher(v.first) * 31 + int_hasher(v.second);
    }
};

//template <class K>
//using hash_set = gp_hash_table<K, null_type, chash>;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e17;
const ll mod = 1e9+7, mod2 = 998244353;
const ld eps = 1e-9;
const bool local = false;

//RINIT;
const int logn = 21, maxn = 200001, maxm = 1, maxn2 = 3;	

vector<int> g[maxn];
int a[maxn];
int dp[maxn][2][2]; // first for final state, second for did we toggle state.

void dfs(int v, int p = -1) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) dp[v][i][j] = inf;
	}
	
	int ct = 0;
	for (int u: g[v]) {
		if (u == p) continue;
		ct++;
		dfs(u, v);
	}
	
	if (ct == 0) {
		if (a[v] == 0) {
			dp[v][0][0] = 0;
			dp[v][1][1] = 1;
		} else {
			dp[v][1][0] = 0;
			dp[v][0][1] = 1;
		}
		return;
	}
	
	for (int t = 0; t < 2; t++) {
		ll v0 = 0, v1 = inf;
		for (int u: g[v]) {
			if (u == p) continue;
			
			ll nv0 = min(v0 + dp[u][t][0], v1 + dp[u][t][1]);
			ll nv1 = min(v1 + dp[u][t][0], v0 + dp[u][t][1]);
			v0 = nv0;
			v1 = nv1;
		}
		v0 += t;
		v1 += t;
		dp[v][(t + a[v]) % 2][t] = min((ll)inf, v0);
		dp[v][(t + a[v] + 1) % 2][t] = min((ll)inf, v1);
	}
}

int main() {
	FAST;
	
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for (int i = 0; i < n; i++) cin >> a[i];
	
	dfs(0);
	
	int res = min(dp[0][0][0], dp[0][0][1]);
	if (res >= inf) {
		cout << "impossible" << nl;
	} else {
		cout << res << nl;
	}
}

// © Benq 
/* stuff you should look for
	* int overflow, array bounds	
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30