結果

問題 No.277 根掘り葉掘り
ユーザー koba-e964koba-e964
提出日時 2015-09-10 10:44:10
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 206 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 515 ms
コンパイル使用メモリ 67,840 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-07-19 05:12:11
合計ジャッジ時間 3,687 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <queue>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef pair<int, int> PI;
const int N = 100100;
VI edges[N];
int rd[N], ld[N];
VI leaves;
void dfs(int v, int par = -1) {
if (par == -1) {
rd[v] = 0;
} else {
rd[v] = rd[par] + 1;
}
int child = 0;
REP(i, 0, edges[v].size()) {
int w = edges[v][i];
if (w == par) { continue; }
dfs(w, v);
child++;
}
if (child == 0) {
leaves.push_back(v);
}
}
void bfs(void) {
queue<PI> que;
REP(i, 0, leaves.size()) {
que.push(PI(leaves[i], 0));
}
while (!que.empty()) {
PI t = que.front(); que.pop();
int x = t.first;
int d = t.second;
if (ld[x] >= 0) {
continue;
}
REP(i, 0, edges[x].size()) {
int y = edges[x][i];
que.push(PI(y, d + 1));
}
ld[x] = d;
}
}
int main(void){
int n;
cin >> n;
REP(i, 0, n - 1) {
int x, y;
cin >> x >> y;
x--, y--;
edges[x].push_back(y);
edges[y].push_back(x);
}
REP(i, 0, n) {
rd[i] = -1;
ld[i] = -1;
}
dfs(0);
bfs();
REP(i, 0, n) {
cout << min(rd[i], ld[i]) << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0