結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
|
提出日時 | 2018-12-16 04:01:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 1,329 bytes |
コンパイル時間 | 821 ms |
コンパイル使用メモリ | 80,020 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-09-25 06:25:41 |
合計ジャッジ時間 | 4,524 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <functional>using namespace std;bool T[100000];bool N[100000];bool ans[100000];vector<int> g[100000];void dfs(int u, int p) {for (int v : g[u]) if (v != p) {dfs(v, u);T[u] |= !N[v];N[u] |= !T[v];}}void dfs2(int u, int p) {const int m = g[u].size();vector<bool> LT(m + 1);vector<bool> LN(m + 1);vector<bool> RT(m + 1);vector<bool> RN(m + 1);for (int i = 0; i < m; i++) {int v = g[u][i];LT[i + 1] = LT[i] || !N[v];LN[i + 1] = LN[i] || !T[v];}for (int i = m - 1; i >= 0; i--) {int v = g[u][i];RT[i] = RT[i + 1] || !N[v];RN[i] = RN[i + 1] || !T[v];}ans[u] = !LN[m];for (int i = 0; i < m; i++) {int v = g[u][i];if (v == p) continue;T[u] = LT[i] || RT[i + 1];N[u] = LN[i] || RN[i + 1];dfs2(v, u);}}int main() {int n;cin >> n;for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;u--;v--;g[u].push_back(v);g[v].push_back(u);}dfs(0, -1);dfs2(0, -1);cout << count(ans, ans + n, true) << endl;for (int i = 0; i < n; i++) {if (ans[i]) {cout << i + 1 << endl;}}}