제출 #545188

#제출 시각아이디문제언어결과실행 시간메모리
545188Zhora_004The Xana coup (BOI21_xanadu)C++17
30 / 100
771 ms66016 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 = 1e5 + 1, inf = 1e9; int n; vector<int> on; vector<vector<int>> tree; bool tc1() { return n <= 20; } bool tc2() { return n <= 40; } ll convert(vector<int>& v) { ll res = 0, p = 1; for (int i = sz(v) - 1; i >= 0; i--) { if (v[i]) res += p; p <<= 1; } return res; } bool tc3() { for (int a = 0; a < n; a++) for (int& b : tree[a]) if (abs(a - b) != 1) return 0; return 1; } 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]; /*if (tc1()) { 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; }*/ if (tc2()) { int ans = 1e9; int k = (n - 1) / 2; int cnt = k + 1; map<ll, int> mp; ll req = convert(on); for (int mask = 0; mask < (1 << cnt); mask++) { vector<int> tmp = vector<int>(n); int ones = 0; for (int i = 0; i < cnt; i++) { if ((mask >> i) & 1) { int u = cnt - i - 1; tmp[u] ^= 1; for (int& v : tree[u]) tmp[v] ^= 1; ones++; } } ll num = convert(tmp); if (mp.find(num) == mp.end()) mp[num] = ones; else mp[num] = min(mp[num], ones); } cnt = n - 1 - (k + 1) + 1; for (int mask = 0; mask < (1 << cnt); mask++) { vector<int> tmp = vector<int>(n); int ones = 0; for (int i = 0; i < cnt; i++) { if ((mask >> i) & 1) { int u = n - i - 1; tmp[u] ^= 1; for (int& v : tree[u]) tmp[v] ^= 1; ones++; } } ll num = convert(tmp); if (mp.find(req ^ num) != mp.end()) ans = min(ans, mp[req ^ num] + ones); } if (ans == 1e9) cout << "impossible"; else cout << ans; return 0; } if (tc3()) { vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2))); if (on[0]) { dp[0][0][0] = inf; dp[0][0][1] = 1; dp[0][1][0] = 0; dp[0][1][1] = inf; } else { dp[0][0][0] = 0; dp[0][0][1] = inf; dp[0][1][0] = inf; dp[0][1][1] = 1; } for (int i = 1; i < n; i++) { if (on[i]) { dp[i][0][0] = dp[i - 1][0][1]; dp[i][0][1] = dp[i - 1][1][0] + 1; dp[i][1][0] = dp[i - 1][0][0]; dp[i][1][1] = dp[i - 1][1][1] + 1; } else { dp[i][0][0] = dp[i - 1][0][0]; dp[i][0][1] = dp[i - 1][1][1] + 1; dp[i][1][0] = dp[i - 1][0][1]; dp[i][1][1] = dp[i - 1][1][0] + 1; } } int ans = min(dp[n - 1][0][0], dp[n - 1][0][1]); if (ans > n) 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...