結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
|
提出日時 | 2023-02-03 22:02:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,087 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 174,520 KB |
実行使用メモリ | 41,472 KB |
最終ジャッジ日時 | 2024-07-02 19:57:37 |
合計ジャッジ時間 | 6,329 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, u, v; cin >> n; vector<vector<int>> g(n); vector<int> c(n), wv; for(int i = 1; i < n; i++){ cin >> u >> v; g[--u].push_back(--v); g[v].push_back(u); } for(int i = 0; i < n; i++){ cin >> c[i]; if(c[i] == 0)wv.push_back(i); } if(wv.size() & 1){ cout << -1 << '\n'; return 0; } vector<vector<int>> dp(n, vector<int>(2, 1 << 29)); function<void(int,int)> dfs = [&](int v, int p){ vector<int>& temp = dp[v]; temp[c[v] ^ 1] = 0; for(auto &&u:g[v]){ if(u == p)continue; dfs(u, v); vector<int> nxt(2, 1 << 30); for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ nxt[i ^ j] = min(nxt[i ^ j], temp[i] + dp[u][j] + j); } } swap(temp, nxt); } }; dfs(0, -1); cout << dp[0][0] << '\n'; }