Submission #529635

#	Time	Username	Problem	Language	Result	Execution time	Memory
529635		hohohaha	The Xana coup (BOI21_xanadu)	C++14	100 / 100	82 ms	21188 KiB

xanadu

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

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' ' 
#define endl '\n'
#define int long long

const int maxn = 2e5 + 5, inf = LLONG_MAX / 100ll; 
int n; 
vi g[maxn]; 
int ini[maxn]; 
int dp[maxn][2][2]; 
int nw[2][2]; 
void dfs(int u, int p ) { 
	dp[u][ini[u]][0] = 0;
	dp[u][ini[u] ^ 1][1] = 1; 
	for(int v: g[u]) { 
		if(v - p) { 
			dfs(v, u);
			fori(s, 0, 1) fori(var, 0, 1) nw[s][var] = inf; 
			fori(var, 0, 1) { 
				fori(s, 0, 1) { 
					fori(var_v, 0, 1) { 	
						nw[s ^ var_v][var] = min(nw[s ^ var_v][var], dp[u][s][var] + dp[v][var][var_v]);
					}
				}
			}
			fori(s, 0, 1) fori(var, 0, 1) dp[u][s][var] = nw[s][var]; 
		}
	}
//	fori(s, 0, 1) { 
//		fori(var, 0, 1) { 
//			cout << u << sp << s << sp << var << sp << dp[u][s][var] << endl; 
//		}
//	}
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);  
	cin >> n; 
	fori(i, 1, n - 1) { 
		int u, v; 
		cin >> u >> v; 
		g[u].eb(v); g[v].eb(u); 
	}
	fori(i, 1, n) cin >> ini[i]; 
	fori(i, 1, n) { 
		fori(s, 0, 1) { 
			fori(var, 0, 1) { 
				dp[i][s][var] = inf; 
			}
		}
	}
	dfs(1, 1); 
	int ans = min(dp[1][0][0], dp[1][0][1]); 
	if(ans == inf) { 
		cout << "impossible" << endl; 
	}
	else cout << ans; 
}

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