제출 #526019

#제출 시각아이디문제언어결과실행 시간메모리
526019GurbanThe Xana coup (BOI21_xanadu)C++17
10 / 100
50 ms17024 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn=1e5+5; int n; int dp[maxn][2][2]; int col[maxn]; vector<int>E[maxn]; void dfs(int nd,int pr){ if(!col[nd]){ dp[nd][0][0] = 0; dp[nd][0][1] = 1e9; dp[nd][1][0] = 1e9; dp[nd][1][1] = 1; } else { dp[nd][1][0] = 0; dp[nd][1][1] = 1e9; dp[nd][0][0] = 1e9; dp[nd][0][1] = 1; } int now[2][2]; for(int i = 0;i < 2;i++) for(int j = 0;j < 2;j++) now[i][j] = 0; for(auto i : E[nd]) if(i != pr){ dfs(i,nd); now[0][0] = min(dp[nd][0][0] + dp[i][0][0],dp[nd][1][0] + dp[i][0][1]); now[0][1] = min(dp[nd][0][1] + dp[i][1][0],dp[nd][1][1] + dp[i][1][1]); now[1][0] = min(dp[nd][0][0] + dp[i][0][1],dp[nd][1][0] + dp[i][0][0]); now[1][1] = min(dp[nd][0][1] + dp[i][1][1],dp[nd][1][1] + dp[i][1][0]); for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) dp[nd][j][k] = now[j][k]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1;i < n;i++){ int x,y; cin >> x >> y; E[x].push_back(y); E[y].push_back(x); } for(int i = 1;i <= n;i++) cin >> col[i]; dfs(1,0); int ans = min(dp[1][0][0],dp[1][0][1]); if(ans >= 1e9) cout<<"impossible"; else cout<<ans; }
#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...