제출 #871416

#제출 시각아이디문제언어결과실행 시간메모리
871416Cyber_WolfThe Xana coup (BOI21_xanadu)C++17
10 / 100
74 ms19096 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const lg N = 2e5+5; vector<lg> adj[N]; lg dp[N][2][2], col[N]; // lg solve(lg src, lg b, lg par) // { // auto&ret = dp[src][b]; // if(~ret) return ret; // ret = 1e18; // for(int i = 0; i < (1ll << adj[src].size()); i++) // { // lg x = (b^(__builtin_popcount(i)&1)); // for(int j = 0; j < adj[src].size(); j++) // { // // } // } // return ret; // } //par true -> must //par false -> must not lg newcol[N]; int main() { lg n; cin >> n; for(int i = 1; i < n; i++) { lg u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 1; i <= n; i++) { cin >> col[i]; } // lg ans = 1e18; // for(int i = 0; i < (1ll << n); i++) // { // for(int j = 0; j < n; j++) // { // newcol[j+1] ^= col[j+1]; // if((1ll << j)&i) // { // for(auto it : adj[j+1]) // { // newcol[it] ^= 1; // } // newcol[j+1] ^= 1; // } // } // lg valid = 1; // for(int j = 1; j <= n; j++) // { // valid &= (newcol[j] == 0); // newcol[j] = 0; // } // lg x = __builtin_popcount(i); // if(valid) ans = min(ans, x); // // if(valid) cout << i << '\n'; // } // if(ans > n) // { // cout << "impossible\n"; // return 0; // } // cout << ans << '\n'; // return 0; // for(int i = 1; i <= n; i++) // { // memset(dp, -1, sizeof(dp)); // ans = min(ans, dfs(i, 0, -1)); // } memset(dp, 0x3f, sizeof(dp)); dp[0][0][0] = dp[0][1][0] = 0; 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] = min(dp[i][j][k], dp[i-1][k][col[i]^j^k]+k); if(dp[i][j][k] > n) dp[i][j][k] = n+1; // cout << dp[i][j][k] << ' '; } } // cout << '\n'; } if(min(dp[n][0][1], dp[n][0][0]) > n) { cout << "impossible\n"; return 0; } cout << min(dp[n][0][0], dp[n][0][1]) << '\n'; }
#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...