結果

問題 No.277 根掘り葉掘り
ユーザー tottoripapertottoripaper
提出日時 2015-09-28 22:32:53
言語 C++11
(gcc 8.5.0)
結果
AC  
実行時間 69 ms / 3,000 ms
コード長 1,358 bytes
コンパイル時間 1,061 ms
使用メモリ 10,804 KB
最終ジャッジ日時 2023-02-17 20:06:02
合計ジャッジ時間 2,915 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 4 ms
8,296 KB
testcase_01 AC 3 ms
8,244 KB
testcase_02 AC 4 ms
7,600 KB
testcase_03 AC 3 ms
7,612 KB
testcase_04 AC 3 ms
7,660 KB
testcase_05 AC 3 ms
8,296 KB
testcase_06 AC 3 ms
8,236 KB
testcase_07 AC 3 ms
8,308 KB
testcase_08 AC 4 ms
7,656 KB
testcase_09 AC 67 ms
9,304 KB
testcase_10 AC 51 ms
10,804 KB
testcase_11 AC 61 ms
9,620 KB
testcase_12 AC 63 ms
9,844 KB
testcase_13 AC 69 ms
9,944 KB
testcase_14 AC 64 ms
9,840 KB
testcase_15 AC 60 ms
9,508 KB
testcase_16 AC 62 ms
9,552 KB
testcase_17 AC 59 ms
9,804 KB
testcase_18 AC 60 ms
9,684 KB
testcase_19 AC 60 ms
9,860 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <algorithm>
#include <tuple>
#include <queue>

typedef std::tuple<int,int> P;

const int INF = 252521;

int dr[100001], dl[100001];
std::vector<int> G[100001];

void computeDistance(int (&d)[100001], std::vector<int> initialPoss){    
    std::queue<P> queue;
    for(int v : initialPoss){
        queue.push(std::make_tuple(v, 0));
        d[v] = 0;
    }

    while(!queue.empty()){
        int u, c;
        std::tie(u, c) = queue.front();
        queue.pop();

        if(d[u] < c){continue;}

        for(int v : G[u]){
            if(d[v] > d[u] + 1){
                d[v] = d[u] + 1;
                queue.push(std::make_tuple(v, d[v]));
            }
        }
    }
}

int main(){
    int N;
    scanf("%d", &N);
    
    std::fill(dr, dr+N+1, INF);
    std::fill(dl, dl+N+1, INF);

    for(int i=0;i<N-1;i++){
        int x, y;
        scanf("%d %d", &x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    computeDistance(dr, {1});
    
    std::vector<int> leaves;
    for(int i=1;i<=N;i++){
        bool isLeaf = true;
        for(int u : G[i]){
            if(dr[u] > dr[i]){
                isLeaf = false;
            }
        }

        if(isLeaf){leaves.push_back(i);}
    }

    computeDistance(dl, leaves);

    for(int i=1;i<=N;i++){
        printf("%d\n", std::min(dr[i], dl[i]));
    }
}
0