結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2015-09-04 22:42:45 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 204 ms / 3,000 ms |
コード長 | 1,113 bytes |
コンパイル時間 | 1,739 ms |
コンパイル使用メモリ | 161,764 KB |
実行使用メモリ | 15,872 KB |
最終ジャッジ日時 | 2024-07-19 01:20:17 |
合計ジャッジ時間 | 4,779 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a) for (int i = 0; i < (a); i++) #define rep2(i, a, b) for (int i = (a); i < (b); i++) #define repr(i, a) for (int i = (a) - 1; i >= 0; i--) #define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--) using namespace std; typedef long long ll; const int inf = 1e9; int N; vector<int> G[101010]; int R[101010]; int L[101010]; void dfs(int curr, int prev) { for (int next : G[curr]) if (next != prev) { R[next] = R[curr] + 1; dfs(next, curr); } } int dfs2(int curr, int prev) { int res = inf; bool leaf = true; for (int next : G[curr]) if (next != prev) { int d = dfs2(next, curr); res = min(res, d + 1); leaf = false; } if (leaf) return L[curr] = 0; return L[curr] = res; } void dfs3(int curr, int prev) { for (int next : G[curr]) if (next != prev) { L[next] = min(L[next], L[curr] + 1); dfs3(next, curr); } } int main() { cin >> N; rep (i, N - 1) { int x, y; cin >> x >> y; x--; y--; G[x].push_back(y); G[y].push_back(x); } dfs(0, -1); dfs2(0, -1); dfs3(0, -1); rep (i, N) { cout << min(R[i], L[i]) << endl; } return 0; }