結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2018-12-19 01:56:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 1,265 bytes |
コンパイル時間 | 2,301 ms |
コンパイル使用メモリ | 199,924 KB |
最終ジャッジ日時 | 2025-01-06 19:39:43 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:33:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | scanf("%d%d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, N) for (int i = 0; i < (N); i++)#define all(a) (a).begin(), (a).end()#define pb push_backusing ll = long long;using i_i = tuple<int, int>;void dfs_down(int u, int p, vector<vector<int>>& G, vector<bool>& down) {down[u] = true;for (int v: G[u]) if (v != p) {dfs_down(v, u, G, down);if (down[v]) down[u] = false;}}void dfs_up(int u, int p, vector<vector<int>>& G, vector<bool>& down, vector<bool>& up) {int cnt = up[u];for (int v: G[u]) if (v != p) cnt += down[v];for (int v: G[u]) if (v != p) {up[v] = (cnt - down[v] == 0);dfs_up(v, u, G, down, up);}}int main() {int N; cin >> N;vector<vector<int>> G(N);rep(i, N - 1) {int u, v;scanf("%d%d", &u, &v);u--; v--;G[u].pb(v);G[v].pb(u);}vector<bool> down(N);dfs_down(0, -1, G, down);vector<bool> up(N);dfs_up(0, -1, G, down, up);vector<int> V;rep(u, N) if (down[u] && !up[u]) V.pb(u);int M = V.size();cout << M << endl;rep(j, M) printf("%d\n", V[j] + 1);// rep(u, N) cout << down[u];// cout << endl;// rep(u, N) cout << up[u];// cout << endl;}