Submission #444413

#	Time	Username	Problem	Language	Result	Execution time	Memory
444413		limabeans	The Xana coup (BOI21_xanadu)	C++17	100 / 100	123 ms	24692 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







const int maxn = 1e5 + 5;
const int inf = 1e7;


void setmin(int &x, int y) {
    x = min(x, y);
}

int n;
vector<int> g[maxn];
int a[maxn];

int dp[maxn][2][2];

//dp[at][value][flip/noflip] = min flips

void dfs(int at, int p) {
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }

    for (int flip: {0,1}) {
	dp[at][a[at]^flip][flip] = flip;
	dp[at][a[at]^flip^1][flip] = inf;
	
	for (int to: g[at]) {
	    if (to == p) continue;
	    vector<int> ndp = {inf, inf};
	    for (int tval: {0,1}) {
		if ((tval^flip) == 0) {
		    for (int tflip: {0,1}) {
			for (int aval: {0,1}) {
			    setmin(ndp[aval^tflip], dp[at][aval][flip]+dp[to][tval][tflip]);
			}
		    }
		}
	    }
	    
	    dp[at][0][flip] = ndp[0];
	    dp[at][1][flip] = ndp[1];
	}
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    dfs(0, -1);

    // for (int v: {0,1}) {
    // 	for (int f: {0,1}) {
    // 	    cout<<v<<" "<<f<<": "<<dp[0][v][f]<<endl;
    // 	}
    // }

    int ans = inf;
    for (int flip: {0,1}) {
	ans = min(ans, dp[0][0][flip]);
    }

    if (ans == inf) out("impossible");
    out(ans);
    
    return 0;
}

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