結果

問題 No.277 根掘り葉掘り
ユーザー koba-e964koba-e964
提出日時 2015-09-10 10:44:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 232 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 68,032 KB
実行使用メモリ 14,288 KB
最終ジャッジ日時 2023-09-26 10:24:46
合計ジャッジ時間 4,627 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,712 KB
testcase_01 AC 4 ms
5,768 KB
testcase_02 AC 3 ms
5,700 KB
testcase_03 AC 4 ms
5,828 KB
testcase_04 AC 4 ms
5,832 KB
testcase_05 AC 3 ms
5,728 KB
testcase_06 AC 4 ms
5,712 KB
testcase_07 AC 3 ms
5,704 KB
testcase_08 AC 4 ms
5,708 KB
testcase_09 AC 226 ms
14,288 KB
testcase_10 AC 198 ms
11,928 KB
testcase_11 AC 218 ms
10,336 KB
testcase_12 AC 228 ms
13,056 KB
testcase_13 AC 232 ms
10,872 KB
testcase_14 AC 218 ms
10,948 KB
testcase_15 AC 218 ms
10,916 KB
testcase_16 AC 218 ms
10,848 KB
testcase_17 AC 219 ms
10,632 KB
testcase_18 AC 219 ms
10,552 KB
testcase_19 AC 222 ms
10,560 KB
権限があれば一括ダウンロードができます

ソースコード

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;
  }
}
0