제출 #404641

#제출 시각아이디문제언어결과실행 시간메모리
404641nicolaalexandraThe Xana coup (BOI21_xanadu)C++14
10 / 100
140 ms15300 KiB
#include <bits/stdc++.h> #define DIM 100010 #define INF 2000000000 using namespace std; int dp[DIM][2][2],v[DIM]; vector <int> L[DIM]; int n,i,x,y; void dfs (int nod, int tata){ int ok = 0; for (auto vecin : L[nod]) if (vecin != tata){ ok = 1; dfs (vecin,nod); } if (!ok){ dp[nod][v[nod]][0] = 0; dp[nod][1-v[nod]][1] = 1; } else { /// caz 1: nu dau switch in nod int sum = 0, cnt = 0; for (auto vecin : L[nod]){ if (vecin == tata) continue; if (dp[vecin][0][0] < dp[vecin][0][1]) sum += dp[vecin][0][0]; else { sum += dp[vecin][0][1]; cnt++; } } if (cnt % 2 == 0) dp[nod][v[nod]][0] = sum; else dp[nod][1-v[nod]][0] = sum; /// incerc sa schimb paritatea lui cnt int mini = INF; for (auto vecin : L[nod]){ if (vecin == tata) continue; if (dp[vecin][0][0] < dp[vecin][0][1]) mini = min (mini,sum - dp[vecin][0][0] + dp[vecin][0][1]); else mini = min (mini,sum - dp[vecin][0][1] + dp[vecin][0][0]); } if (cnt % 2 == 0) dp[nod][1-v[nod]][0] = mini; else dp[nod][v[nod]][0] = mini; /// caz 2: dau switch in nod cnt = 1, sum = 0; for (auto vecin : L[nod]){ if (vecin == tata) continue; if (dp[vecin][1][0] < dp[vecin][1][1]) sum += dp[vecin][1][0]; else { sum += dp[vecin][1][1]; cnt++; } } if (cnt % 2 == 0) dp[nod][v[nod]][1] = 1 + sum; else dp[nod][1-v[nod]][1] = 1 + sum; /// schimb starea din nod mini = INF; for (auto vecin : L[nod]){ if (vecin == tata) continue; if (dp[vecin][1][0] < dp[vecin][1][1]) mini = min (mini,sum - dp[vecin][1][0] + dp[vecin][1][1]); else mini = min (mini, sum - dp[vecin][1][1] + dp[vecin][1][0]); } if (cnt % 2 == 0) dp[nod][1-v[nod]][1] = 1 + mini; else dp[nod][v[nod]][1] = 1 + mini; } } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n; for (i=1;i<n;i++){ cin>>x>>y; L[x].push_back(y); L[y].push_back(x); } for (i=1;i<=n;i++){ cin>>v[i]; dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = INF; } dfs (1,0); int sol = min(dp[1][0][0],dp[1][0][1]); if (sol == INF) cout<<"impossible"; else cout<<sol; 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...