제출 #677150

#제출 시각아이디문제언어결과실행 시간메모리
677150Melika0ghThe Xana coup (BOI21_xanadu)C++17
30 / 100
55 ms15488 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define sync ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define pb push_back #define pii pair<int, int> #define mp make_pair #define fi first #define se second const int maxn = 1e5 + 2, inf = 1e7; vector<int> adj[maxn]; int dp[maxn][2][2]; int sit[maxn]; int n; void Dfs(int v, int p) { for(int u : adj[v]) { if(u != p) Dfs(u, v); } if(adj[v].size() == 1) { dp[v][sit[v]][0] = 0; dp[v][1 - sit[v]][1] = 1; return; } int sum[2] = {0, 0}, w[2] = {inf, inf}, cnt[2] = {0, 0}; for(int u : adj[v]) { if(u == p) continue; sum[0] += min(dp[u][0][0], dp[u][0][1]); sum[1] += min(dp[u][1][0], dp[u][1][1]); w[0] = min(w[0], max(dp[u][0][0], dp[u][0][1]) - min(dp[u][0][0], dp[u][0][1])); w[1] = min(w[1], max(dp[u][1][0], dp[u][1][1]) - min(dp[u][1][0], dp[u][1][1])); cnt[0] += (dp[u][0][0] >= dp[u][0][1]); cnt[1] += (dp[u][1][0] >= dp[u][1][1]); } dp[v][sit[v]][0] = sum[0] + (cnt[0] % 2 ? w[0] : 0); dp[v][1 - sit[v]][0] = sum[0] + (cnt[0] % 2 ? 0 : w[0]); dp[v][sit[v]][1] = sum[1] + 1 + (cnt[1] % 2 ? 0 : w[1]); dp[v][1 - sit[v]][1] = sum[1] + 1 + (cnt[1] % 2 ? w[1] : 0); return; } int main() { sync; cin >> n; int r = 0; for(int i = 0; i < n-1; i++) { int v, u; cin >> v >> u; v--, u--; adj[v].pb(u); adj[u].pb(v); if(adj[v].size() > 1) r = v; if(adj[u].size() > 1) r = u; } for(int i = 0; i < n; i++) cin >> sit[i]; for(int i = 0; i < n; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) dp[i][j][k] = inf; Dfs(r, -1); int ans = min(dp[r][0][0], dp[r][0][1]); if(ans > n) cout << "impossible" << '\n'; else cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...