Submission #526031

#TimeUsernameProblemLanguageResultExecution timeMemory
526031GurbanThe Xana coup (BOI21_xanadu)C++17
100 / 100
58 ms16836 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn=1e5+5; int n; int col[maxn]; ll dp[maxn][2][2]; vector<int>E[maxn]; void dfs(int nd,int pr){ if((int)E[nd].size() == 1 and E[nd][0] == pr){ if(!col[nd]){ dp[nd][0][0] = 0; dp[nd][0][1] = 1e6; dp[nd][1][0] = 1e6; dp[nd][1][1] = 1; } else { dp[nd][1][0] = 0; dp[nd][1][1] = 1e6; dp[nd][0][0] = 1e6; dp[nd][0][1] = 1; } return; } for(auto i : E[nd]) if(i != pr) dfs(i,nd); if(!col[nd]){ ll bef[2]; bef[0] = 0,bef[1] = 1e6; for(auto i : E[nd]) if(i != pr){ ll now[2]; now[0] = min(bef[0] + dp[i][0][0],bef[1] + dp[i][0][1]); now[1] = min(bef[0] + dp[i][0][1],bef[1] + dp[i][0][0]); bef[0] = now[0]; bef[1] = now[1]; } dp[nd][0][0] = bef[0]; dp[nd][1][0] = bef[1]; bef[0] = 0,bef[1] = 1e6; for(auto i : E[nd]) if(i != pr){ ll now[2]; now[0] = min(bef[0] + dp[i][1][0],bef[1] + dp[i][1][1]); now[1] = min(bef[0] + dp[i][1][1],bef[1] + dp[i][1][0]); bef[0] = now[0]; bef[1] = now[1]; } dp[nd][0][1] = bef[1] + 1; dp[nd][1][1] = bef[0] + 1; } else { ll bef[2]; bef[0] = 0,bef[1] = 1e6; for(auto i : E[nd]) if(i != pr){ ll now[2]; now[0] = min(bef[0] + dp[i][0][0],bef[1] + dp[i][0][1]); now[1] = min(bef[0] + dp[i][0][1],bef[1] + dp[i][0][0]); bef[0] = now[0]; bef[1] = now[1]; } dp[nd][0][0] = bef[1]; dp[nd][1][0] = bef[0]; bef[0] = 0,bef[1] = 1e6; for(auto i : E[nd]) if(i != pr){ ll now[2]; now[0] = min(bef[0] + dp[i][1][0],bef[1] + dp[i][1][1]); now[1] = min(bef[0] + dp[i][1][1],bef[1] + dp[i][1][0]); bef[0] = now[0]; bef[1] = now[1]; } dp[nd][0][1] = bef[0] + 1; dp[nd][1][1] = bef[1] + 1; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1;i <= n;i++) for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) dp[i][j][k] = 1e6; 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); // for(int i = 1;i <= n;i++){ // cout<<i<<' '; // for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) cout<<dp[i][j][k]<<' '; // cout<<'\n'; // } ll ans = min(dp[1][0][0],dp[1][0][1]); if(ans >= 1e6) 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...