結果

問題 No.806 木を道に
ユーザー @abcde
提出日時 2019-03-27 01:35:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,335 bytes
コンパイル時間 1,688 ms
コンパイル使用メモリ 167,840 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-10-11 01:38:33
合計ジャッジ時間 5,490 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 8 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

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