結果

問題 No.277 根掘り葉掘り
コンテスト
ユーザー tottoripaper
提出日時 2015-09-28 22:32:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 56 ms / 3,000 ms
コード長 1,358 bytes
コンパイル時間 618 ms
コンパイル使用メモリ 56,292 KB
実行使用メモリ 10,960 KB
最終ジャッジ日時 2024-07-19 11:25:58
合計ジャッジ時間 2,275 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:45:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

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