結果
| 問題 | No.768 Tapris and Noel play the game on Treeone |
| ユーザー |
 lumc_
|
| 提出日時 | 2018-03-12 01:31:24 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 991 bytes |
| コンパイル時間 | 1,668 ms |
| コンパイル使用メモリ | 174,608 KB |
| 実行使用メモリ | 817,792 KB |
| 最終ジャッジ日時 | 2024-10-02 02:29:38 |
| 合計ジャッジ時間 | 4,832 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| 20evil_special_uni1.txt | -- | - |
| 20evil_special_uni2.txt | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100000];
int N;
// 想定MLE ?
auto dp = vector< vector<char> >(100000, vector<char>(100000, -1));
bool dfs(int v, int p) {
if(~((int)dp[v][p])) return (int) dp[v][p];
bool flag = 0;
for(int u : g[v]) if(u != p) flag |= dfs(u, v);
return dp[v][p] = !flag;
}
bool isTree() {
bool flag[N] = {};
function<void(int, int)> check = [&](int v, int p) {
flag[v] = 1;
for(int u : g[v]) if(u != p) check(u, v);
};
check(0, -1);
bool all = 1;
for(int i = 0; i < N; i++) all &= flag[i];
return all;
}
int main() {
cin >> N;
for(int i = 0; i < N - 1; i++) {
int a, b; cin >> a >> b; a--; b--;
assert(0 <= a && a < N && 0 <= b && b < N);
g[a].emplace_back(b);
g[b].emplace_back(a);
}
assert(isTree());
vector<int> ans; ans.reserve(N);
for(int i = 0; i < N; i++)
if(dfs(i, -1)) ans.emplace_back(i);
cout << ans.size() << endl;
for(int el : ans) cout << el + 1 << endl;
}