結果

問題 No.277 根掘り葉掘り
ユーザー finefine
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0