제출 #545172

#제출 시각아이디문제언어결과실행 시간메모리
545172Zhora_004The Xana coup (BOI21_xanadu)C++17
5 / 100
1088 ms7876 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <string> #include <sstream> #include <iomanip> #include <map> #include <unordered_map> #include <stack> #include <cstdio> #include <climits> #include <tuple> #include <ctime> #include <cstring> #include <numeric> #include <functional> #include <chrono> #include <cassert> #include <bitset> //#include <bit> //#include <ranges> //#include <numbers> #define itn int #define sacnf scanf #define sz(a) ((int)((a).size())) // printf("%.10f\n", ans); using ll = long long; using namespace std; const ll mod = 1e9 + 7; const int N = 1e6 + 1, inf = 1e9; int n; vector<int> on; vector<vector<int>> tree; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; on = vector<int>(n); tree = vector<vector<int>>(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; tree[--u].push_back(--v); tree[v].push_back(u); } for (int i = 0; i < n; i++) cin >> on[i]; int ans = 1e9; for (int mask = 0; mask < (1 << n); mask++) { vector<int> tmp = on; int cnt = 0; for (int i = 0; i < n; i++) { if ((mask >> i) & 1) { int u = n - i - 1; tmp[u] ^= 1; for (int& v : tree[u]) tmp[v] ^= 1; cnt++; } } bool flag = 1; for (int i = 0; i < n; i++) { if (tmp[i]) { flag = 0; break; } } if (flag) ans = min(ans, cnt); } if (ans == 1e9) cout << "impossible"; else cout << ans; 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...