Submission #1203339

#TimeUsernameProblemLanguageResultExecution timeMemory
1203339AlgorithmWarriorThe Xana coup (BOI21_xanadu)C++20
100 / 100
60 ms17124 KiB
#include <bits/stdc++.h> using namespace std; int const INF=1e9; int const MAX=1e5+5; int dp[MAX][2][2]; /// dp[nod][i][j]=nr minim de schimbari sa stingem tot subarborele /// lui nod astfel incat nod sa aiba valoarea i si am aplicat /// toggle sau nu pe acest nod int aux[MAX][2][2]; int n; vector<int>tree[MAX]; bool v[MAX]; void read(){ cin>>n; int i; for(i=1;i<n;++i){ int u,v; cin>>u>>v; tree[u].push_back(v); tree[v].push_back(u); } for(i=1;i<=n;++i) cin>>v[i]; } void dfs(int nod,int tata){ int i; for(i=0;i<2;++i){ aux[nod][i][0]=0; aux[nod][i][1]=INF; } for(auto fiu : tree[nod]) if(fiu!=tata){ dfs(fiu,nod); for(i=0;i<2;++i){ int aux0=min(aux[nod][i][0]+dp[fiu][i][0],aux[nod][i][1]+dp[fiu][i][1]); int aux1=min(aux[nod][i][0]+dp[fiu][i][1],aux[nod][i][1]+dp[fiu][i][0]); aux[nod][i][0]=min(INF,aux0); aux[nod][i][1]=min(INF,aux1); } } dp[nod][v[nod]][0]=aux[nod][0][0]; dp[nod][v[nod]][1]=aux[nod][1][1]+1; dp[nod][!v[nod]][0]=aux[nod][0][1]; dp[nod][!v[nod]][1]=aux[nod][1][0]+1; } void write(int ans){ if(ans<INF) cout<<ans; else cout<<"impossible"; } int main() { read(); dfs(1,0); write(min(dp[1][0][0],dp[1][0][1])); 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...