結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2017-03-24 18:45:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 197 ms / 3,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 1,817 ms |
コンパイル使用メモリ | 174,416 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-07-06 02:08:48 |
合計ジャッジ時間 | 4,869 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1e7;vector< vector<int> > G;vector<int> R, L;void dfs(int cur, int par) {for (int nex : G[cur]) {if (nex == par) continue;R[nex] = R[cur] + 1;dfs(nex, cur);L[cur] = min(L[cur], L[nex]);}if (L[cur] == INF) L[cur] = 0;else L[cur]++;}void dfs2(int cur, int par) {if (par != -1) L[cur] = min(L[cur], L[par] + 1);for (int nex : G[cur]) {if (nex == par) continue;dfs2(nex, cur);}}int main() {cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;G.resize(n);for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;x--;y--;G[x].push_back(y);G[y].push_back(x);}R.resize(n, INF);L.resize(n, INF);R[0] = 0;dfs(0, -1);dfs2(0, -1);for (int i = 0; i < n; i++) {cout << min(R[i], L[i]) << endl;}return 0;}