Submission #1096428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096428		vjudge1	The Xana coup (BOI21_xanadu)	C++11	100 / 100	24 ms	17496 KiB

xanadu

#include<bits/stdc++.h>
#define int ll
#define lc (rt<<1)
#define rc (rt<<1)
#define mid (l+r>>1)
#define rg register
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define DEBUG printf("Debug on line %d\n", __LINE__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;

inline int read(){
	int n=0, f=1; char ch = getchar();
	for(; !isdigit(ch); ch=getchar()) if(ch == '-') f=-1;
	for(; isdigit(ch); ch=getchar()) n=n*10+ch-'0';
	return n*f;
}

struct edge{
	int nxt;
	int to;
}g[N<<1];

int n;
int head[N], cnt;
int a[N];
int f[N][2][2];

void add_edge(int u, int v){
	g[++cnt].nxt = head[u];
	g[cnt].to = v;
	head[u] = cnt;
}

void dfs(int u, int fa){
	f[u][0][0] = 0;
	f[u][1][1] = 1;
	f[u][0][1] = f[u][1][0] = INF;
	for(int i=head[u]; i; i=g[i].nxt){
		int v = g[i].to;
		if(v == fa) continue;
		dfs(v, u);
		int x = min(f[u][0][0] + f[v][0][a[v]], f[u][0][1] + f[v][1][a[v]]);
		int y = min(f[u][0][1] + f[v][0][a[v]], f[u][0][0] + f[v][1][a[v]]);
		int z = min(f[u][1][0] + f[v][0][!a[v]], f[u][1][1] + f[v][1][!a[v]]);
		int w = min(f[u][1][1] + f[v][0][!a[v]], f[u][1][0] + f[v][1][!a[v]]);
		f[u][0][0] = x, f[u][0][1] = y, f[u][1][0] = z, f[u][1][1] = w;
	}
		
//	printf("%d f00 = %d, f01 = %d, f10 = %d, f11 = %d\n", u, f[u][0][0], f[u][0][1], f[u][1][0], f[u][1][1]);
}

signed main(){
	n = read();
	for(int i=1; i<n; i++){
		int u = read(), v = read();
		add_edge(u, v);
		add_edge(v, u);
	}
	
	for(int i=1; i<=n; i++){
		a[i] = read(); 
	}
	
	dfs(1, 0);
	
	int ans = min(f[1][0][a[1]], f[1][1][a[1]]);
	if(ans >= INF) printf("impossible\n");
	else printf("%lld\n", ans);
}

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