結果

問題 No.277 根掘り葉掘り
ユーザー koba-e964koba-e964
提出日時 2015-09-10 10:44:10
言語 C++11
(gcc 8.5.0)
結果
AC  
実行時間 214 ms / 3,000 ms
コード長 1,235 bytes
コンパイル時間 470 ms
使用メモリ 14,412 KB
最終ジャッジ日時 2023-02-17 08:39:47
合計ジャッジ時間 4,232 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 3 ms
6,276 KB
testcase_01 AC 4 ms
6,200 KB
testcase_02 AC 3 ms
6,272 KB
testcase_03 AC 3 ms
6,272 KB
testcase_04 AC 3 ms
6,184 KB
testcase_05 AC 4 ms
6,248 KB
testcase_06 AC 3 ms
6,176 KB
testcase_07 AC 3 ms
6,280 KB
testcase_08 AC 3 ms
6,184 KB
testcase_09 AC 210 ms
14,412 KB
testcase_10 AC 185 ms
11,752 KB
testcase_11 AC 205 ms
10,380 KB
testcase_12 AC 211 ms
13,168 KB
testcase_13 AC 214 ms
10,764 KB
testcase_14 AC 202 ms
10,872 KB
testcase_15 AC 209 ms
10,708 KB
testcase_16 AC 206 ms
10,888 KB
testcase_17 AC 201 ms
10,584 KB
testcase_18 AC 204 ms
10,440 KB
testcase_19 AC 206 ms
10,588 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