結果

問題 No.277 根掘り葉掘り
ユーザー tottoripapertottoripaper
提出日時 2015-09-28 22:32:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 65 ms / 3,000 ms
コード長 1,358 bytes
コンパイル時間 902 ms
コンパイル使用メモリ 70,620 KB
実行使用メモリ 10,852 KB
最終ジャッジ日時 2023-09-26 17:27:06
合計ジャッジ時間 2,541 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,336 KB
testcase_01 AC 3 ms
5,328 KB
testcase_02 AC 3 ms
5,388 KB
testcase_03 AC 3 ms
5,372 KB
testcase_04 AC 3 ms
5,400 KB
testcase_05 AC 3 ms
5,340 KB
testcase_06 AC 3 ms
5,328 KB
testcase_07 AC 4 ms
5,420 KB
testcase_08 AC 4 ms
5,360 KB
testcase_09 AC 65 ms
9,292 KB
testcase_10 AC 48 ms
10,852 KB
testcase_11 AC 60 ms
9,624 KB
testcase_12 AC 60 ms
9,760 KB
testcase_13 AC 65 ms
9,892 KB
testcase_14 AC 63 ms
9,860 KB
testcase_15 AC 61 ms
9,528 KB
testcase_16 AC 59 ms
9,520 KB
testcase_17 AC 58 ms
9,848 KB
testcase_18 AC 59 ms
9,608 KB
testcase_19 AC 60 ms
9,820 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