Submission #720899

#TimeUsernameProblemLanguageResultExecution timeMemory
720899JohannThe Xana coup (BOI21_xanadu)C++14
100 / 100
146 ms39544 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define vb vector<bool> #define vi vector<int> #define vpii vector<pii> #define vvb vector<vb> #define vvi vector<vi> #define vvvi vector<vvi> #define vvpii vector<vpii> #define sz(x) (int)(x).size() int N; vi L; vvi adj; vvvi dp; void dfs(int v, int p) { for (int u : adj[v]) if (u != p) dfs(u, v); for (int schalten = 0; schalten < 2; ++schalten) { vvi res(1, vi(2, INT_MAX)); res[0][L[v] ^ schalten] = schalten; int i = 0; for (int u : adj[v]) { if (u == p) continue; res.push_back(vi(2, INT_MAX)); ++i; if (dp[u][schalten][0] != INT_MAX) { if (res[i - 1][0] != INT_MAX) res[i][0] = min(res[i][0], res[i - 1][0] + dp[u][schalten][0]); if (res[i - 1][1] != INT_MAX) res[i][1] = min(res[i][1], res[i - 1][1] + dp[u][schalten][0]); } if (dp[u][schalten][1] != INT_MAX) { if (res[i - 1][1] != INT_MAX) res[i][0] = min(res[i][0], res[i - 1][1] + dp[u][schalten][1]); if (res[i - 1][0] != INT_MAX) res[i][1] = min(res[i][1], res[i - 1][0] + dp[u][schalten][1]); } } dp[v][0][schalten] = res.back()[0]; dp[v][1][schalten] = res.back()[1]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; adj.resize(N); for (int i = 0, a, b; i < N - 1; ++i) { cin >> a >> b; --a, --b; adj[a].push_back(b); adj[b].push_back(a); } L.resize(N); for (int i = 0; i < N; ++i) cin >> L[i]; dp.assign(N, vvi(2, vi(2, INT_MAX))); // [node][res][wurde geschaltet?] dfs(0, 0); int ans = min(dp[0][0][0], dp[0][0][1]); if (ans != INT_MAX) cout << ans << "\n"; else cout << "impossible\n"; 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...