제출 #871412

#제출 시각아이디문제언어결과실행 시간메모리
871412Cyber_WolfThe Xana coup (BOI21_xanadu)C++17
5 / 100
1064 ms14672 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], 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(ans > n) { cout << "impossible\n"; return 0; } cout << ans << '\n'; // for(int i = 1; i <= n; i++) // { // memset(dp, -1, sizeof(dp)); // ans = min(ans, dfs(i, 0, -1)); // } // dp[0][1] = 1e18; for(int i = 1; i <= n; i++) { if(!col[i]) { dp[i][0] = dp[i-1][0]; dp[i][1] = dp[i-1][1]+1; } else{ dp[i][0] = dp[i-1][1]+1; dp[i][1] = dp[i-1][0]; } } // if(dp[n][0] > n) // { // cout << "impossible\n"; // return 0; // } // cout << dp[n][0] << '\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...