제출 #678365

#제출 시각아이디문제언어결과실행 시간메모리
678365VaheThe Xana coup (BOI21_xanadu)C++17
100 / 100
180 ms27648 KiB
#include <iostream> #include <vector> #include <set> #include <queue> #include <deque> #include <map> #include <stack> #include <algorithm> #include <cmath> #include <iomanip> #include <climits> using namespace std; using ll = long long; int n; vector<int> clr; vector<vector<int>> gp; vector<vector<vector<int>>> dp; void DPcreator(int u, int p, int nerk) { multiset<pair<int, int>> st, zibil; bool impossible = 0; int MinChange = 2e9; for (int& v : gp[u]) { if (v == p) continue; if (dp[v][0][nerk] < 2e9 && dp[v][1][nerk] < 2e9) { st.insert({ min(dp[v][0][nerk], dp[v][1][nerk]), (dp[v][0][nerk] < dp[v][1][nerk] ? 0 : 1) }); MinChange = min(MinChange, abs(dp[v][0][nerk] - dp[v][1][nerk])); } else if (dp[v][0][nerk] < 2e9) st.insert({ dp[v][0][nerk], 0 }); else if (dp[v][1][nerk] < 2e9) st.insert({ dp[v][1][nerk], 1 }); else impossible = 1; } int sum = 0, cnt = clr[u] + nerk; for (pair<int, int> i : st) { cnt += i.second; sum += i.first; } int NotChanged = sum + nerk; sum += MinChange; int Changed = sum + nerk; // if (impossible) NotChanged = Changed = 2e9; // if (cnt & 1) dp[u][nerk][0] = Changed, dp[u][nerk][1] = NotChanged; else dp[u][nerk][0] = NotChanged, dp[u][nerk][1] = Changed; } void dfs(int u, int p) { if (gp[u].size() == 1 && u != 0) { if (clr[u]) { dp[u][0][0] = 2e9; dp[u][0][1] = 0; dp[u][1][0] = 1; dp[u][1][1] = 2e9; } else { dp[u][0][0] = 0; dp[u][0][1] = 2e9; dp[u][1][0] = 2e9; dp[u][1][1] = 1; } return; } for (int& v : gp[u]) { if (v == p) continue; if (dp[v][0][0] == -1) dfs(v, u); } DPcreator(u, p, 0); DPcreator(u, p, 1); } int main() { int n; cin >> n; gp = vector<vector<int>>(n); dp = vector<vector<vector<int>>>(n, { {-1, -1}, {-1, -1} }); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; gp[--u].push_back(--v); gp[v].push_back(u); } clr = vector<int>(n); for (int& i : clr) cin >> i; dfs(0, -1); int ans = min(dp[0][0][0], dp[0][1][0]); if (ans >= 2e9) cout << "impossible\n"; else cout << ans << endl; //for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) printf("dp[%d][%d][%d] = %d\n", i + 1, j, k, dp[i][j][k]); puts(""); } 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...