結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2019-03-27 16:53:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,143 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 80,128 KB |
実行使用メモリ | 9,872 KB |
最終ジャッジ日時 | 2024-10-11 02:23:44 |
合計ジャッジ時間 | 3,073 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <vector>#include <iostream>#include <functional>using namespace std;int main() {cin.tie(0);ios_base::sync_with_stdio(false);int N;cin >> N;vector<vector<int> > G(N);for (int i = 0; i < N - 1; ++i) {int a, b;cin >> a >> b; --a, --b;G[a].push_back(b);G[b].push_back(a);}vector<bool> dp_up(N, true), dp_down(N);function<void(int, int)> dfs_up = [&](int pos, int pre) {int cnt = 0;for (int i : G[pos]) {if (i == pre) continue;dfs_up(i, pos);if (dp_up[i]) dp_up[pos] = false;++cnt;}};dfs_up(0, -1);dp_down[0] = true;function<void(int, int)> dfs_down = [&](int pos, int pre) {int sum = 0;for (int i : G[pos]) {if (i == pre) continue;sum += (dp_up[i] ? 1 : 0);}for (int i : G[pos]) {if (i == pre) continue;if (!dp_down[pos]) dp_down[i] = true;if (sum - (dp_up[i] ? 1 : 0) > 0) dp_down[i] = true;dfs_down(i, pos);}};dfs_down(0, -1);vector<int> ans;for (int i = 0; i < N; ++i) {if (dp_up[i] && dp_down[i]) {ans.push_back(i);}}cout << ans.size() << '\n';for (int i : ans) {cout << i + 1 << '\n';}return 0;}