제출 #632626

#제출 시각아이디문제언어결과실행 시간메모리
632626l_rehoThe Xana coup (BOI21_xanadu)C++14
100 / 100
100 ms31696 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #pragma GCC optimize(3) using namespace std; #define ll long long #define x first #define y second #define MOD 1000000007 vector<vector<int>> graph; vector<int> S; vector<vector<vector<ll>>> dp; int N; ll inf = 1e9+5; void dfs(int n, int p){ if((int)graph[n].size() == 1 && n != 0){ if(S[n]){ dp[n][0][0] = inf; dp[n][0][1] = 1; dp[n][1][0] = 0; dp[n][1][1] = inf; } if(!S[n]){ dp[n][0][0] = 0; dp[n][0][1] = inf; dp[n][1][0] = inf; dp[n][1][1] = 1; } return; } ll dp1[2][2]; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ dp1[i][j] = i == 0 ? 0 : inf; } } for(int a : graph[n]){ if(a == p) continue; dfs(a, n); } int i = 0; for(int a : graph[n]){ if(a == p) continue; // numero pari di 1 ll new_0_0; ll new_1_0; ll new_0_1; ll new_1_1; if(!i) new_0_0 = min(inf, dp[a][0][0]); else new_0_0 = min(dp1[1][0] + dp[a][0][1], dp1[0][0] + dp[a][0][0]); // numero dispari di 1 new_1_0 = min(dp1[0][0] + dp[a][0][1], dp1[1][0] + dp[a][0][0]); if(!i) new_0_1 = min(inf, dp[a][1][0]); else new_0_1 = min(dp1[1][1] + dp[a][1][1], dp1[0][1] + dp[a][1][0]); // numero dispari di 1 new_1_1 = min(dp1[0][1] + dp[a][1][1], dp1[1][1] + dp[a][1][0]); dp1[0][0] = new_0_0; dp1[1][0] = new_1_0; dp1[0][1] = new_0_1; dp1[1][1] = new_1_1; i++; } ll min_o_off = dp1[1][0]; ll min_e_off = dp1[0][0]; ll min_o_on = dp1[1][1]; ll min_e_on = dp1[0][1]; // cout<<"DEBUG-->"<<min_o_off<<" "<<min_e_off<<" "<<min_o_on<<" "<<min_e_on<<endl; if(S[n]){ dp[n][0][0] = min_o_off; // tutti i figli devono essere spenti e devo usare min_o dp[n][0][1] = min_e_on+1; dp[n][1][0] = min_e_off; dp[n][1][1] = min_o_on+1; } if(!S[n]){ dp[n][0][0] = min_e_off; // tutti i figli devono essere spenti e devo usare min_o dp[n][0][1] = min_o_on+1; dp[n][1][0] = min_o_off; dp[n][1][1] = min_e_on+1; } } void solve(){ // ifstream in("input.txt"); // ofstream out("output.txt"); cin>>N; graph.assign(N, vector<int>()); dp.assign(N, vector<vector<ll>>(2, vector<ll>(2, inf))); S.assign(N, false); for(int i = 0; i < N-1; i++){ int a, b; cin>>a>>b; a--, b--; graph[a].push_back(b); graph[b].push_back(a); } for(int i = 0; i < N; i++) cin>>S[i]; dfs(0, -1); ll ans = min(dp[0][0][0], dp[0][0][1]); if(ans >= inf) cout<<"impossible"<<endl; else cout<<ans<<endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); 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...