結果

問題 No.277 根掘り葉掘り
ユーザー tottoripapertottoripaper
提出日時 2015-09-28 22:32:53
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,376 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,504 KB
testcase_09 AC 54 ms
9,472 KB
testcase_10 AC 41 ms
10,960 KB
testcase_11 AC 48 ms
9,856 KB
testcase_12 AC 48 ms
9,856 KB
testcase_13 AC 53 ms
10,004 KB
testcase_14 AC 56 ms
9,984 KB
testcase_15 AC 51 ms
9,728 KB
testcase_16 AC 49 ms
9,728 KB
testcase_17 AC 54 ms
9,984 KB
testcase_18 AC 48 ms
9,640 KB
testcase_19 AC 48 ms
9,728 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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