結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
![]() |
提出日時 | 2023-02-10 02:52:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 2,156 ms |
コンパイル使用メモリ | 202,492 KB |
最終ジャッジ日時 | 2025-02-10 11:52:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)#define rrep(i, r, l) for (int i = (int)(r); i > (int)(l); i--)#define all(a) (a).begin(), (a).end()#define rall(a) (a).rbegin(), (a).rend()// 適当に根付き木にする// 深い頂点から白なら黒にする// このとき、親頂点の色も反転// 根以外の全てを黒にした時、根も黒ならOK//void solve() {int n;cin >> n;vector<vector<int>> graph(n, vector<int>());rep(i, 0, n - 1) {int a, b;cin >> a >> b;a--; b--;graph[a].push_back(b);graph[b].push_back(a);}vector<int> color(n), parent(n, -1);rep(i, 0, n) cin >> color[i];int root = 0;queue<int> q;stack<int> stack;q.push(root);while(!q.empty()) {int u = q.front(); q.pop();for (int v: graph[u]) {if (v == parent[u]) {continue;}parent[v] = u;q.push(v);stack.push(v);}}int count = 0;while (!stack.empty()) {int u = stack.top(); stack.pop();if (color[u] == 0) {color[u] = 1;color[parent[u]] ^= 1;count++;}}if (color[root] == 0) {cout << -1 << '\n';} else {cout << count << '\n';}}int main() {int q = 1;// cin >> q;while (q--) {solve();}}