結果

問題 No.806 木を道に
ユーザー @abcde@abcde
提出日時 2019-03-27 01:35:41
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,335 bytes
コンパイル時間 1,489 ms
コンパイル使用メモリ 169,240 KB
実行使用メモリ 13,892 KB
最終ジャッジ日時 2024-04-19 09:04:32
合計ジャッジ時間 5,329 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
6,944 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// AtCoder Beginner Contest 067 (D - Fennec VS. Snuke) を 参照.
// José Marcos氏.
// https://abc067.contest.atcoder.jp/submissions/1424740
// -> 一部改変して, 動作確認した.
// 頂点start と 頂点end との 距離 に関する情報を取得(幅優先探索 Breadth First Search).
int bfs(int start, int end, int size, vector<int> G[]) {
    
    // 1. 各頂点 と 頂点start との 距離 に関する情報を保存.
    vector<int> dist(size + 1, 0);

    // 2. queue の 設定.
    queue<int> Q;
    Q.push(start);
    dist[start] = 0;
    
    // 3. queue が 空になるまで, 探索.
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        // cout << u << " " << dist[u] << endl;
        for(int v : G[u]){
            if(dist[v] == 0){
                dist[v] = dist[u] + 1;
                Q.push(v);
            }
        }
    }
    
    // 4. 頂点start と 頂点end との 距離 を 返却.
    return dist[end];
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<int> G[N + 1];
    // 頂点の時数を保存.
    int d[N + 1];
    for(int i = 0; i <= N; i++) d[i] = 0;
    for(int i = 1; i < N; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        d[a]++, d[b]++;
    }
    
    // 2. 木を道に変換.
    // 2-1. 次数1 の 頂点は？
    vector<int> d1;
    for(int i = 0; i <= N; i++) if(d[i] == 1) d1.push_back(i);

    // 2-2. 次数3以上 の 頂点は？
    vector<int> d3;
    for(int i = 0; i <= N; i++) if(d[i] >= 3) d3.push_back(i);
    
    // 2-3. 各次数3以上 の 頂点と, 次数1 の頂点 の距離は？
    // -> 計算後, 次数3以上の頂点が, 次数2になるために, 必要な組み換え.
    int ans = 0;
    for(auto &p : d3){
        vector<int> v;
        for(auto &q : d1){
            int dist = bfs(p, q, N, G);
            v.push_back(dist);
            cout << "p=" << p << " q=" << q << " dist=" << dist << endl;
        }
        
        // 距離の短い順にsort.
        sort(v.begin(), v.end());
        
        // 距離を順次加算.
        for(int i = 0; i < d[p] - 2; i++) ans += v[i];
    }
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;
    
}
0