結果

問題 No.901 K-ary εxtrεεmε
ユーザー _____TAB__________TAB_____
提出日時 2019-10-04 23:15:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,472 bytes
コンパイル時間 1,170 ms
コンパイル使用メモリ 99,188 KB
実行使用メモリ 62,024 KB
最終ジャッジ日時 2024-10-04 06:25:30
合計ジャッジ時間 10,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
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 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
using namespace std;

void dfs(const vector<vector<pair<long long,int>>> &G, int v, int p, vector<int> &D){
  for(auto e : G[v]){
    long long w;
    int v_;
    tie(w,v_) = e;
    if(v_ == p) continue;
    D[v_] = D[v]+1;
    dfs(G,v_,v,D);
  }
}

int main(){
  int N;
  cin >> N;
  vector<vector<pair<long long,int>>> G(N);
  for(int i = 0; i < N-1; ++i){
    int u, v, w;
    cin >> u >> v >> w;
    G[u].emplace_back(w,v);
    G[v].emplace_back(w,u);
  }
  vector<int> D(N);
  dfs(G,0,-1,D);
  vector<vector<pair<long long,int>>> V(20,vector<pair<long long,int>>(N));
  for(int i = 0; i < N; ++i){
    for(auto e : G[i]){
      int v_ = e.second;
      if(D[i] == D[v_]+1){
        V[0][i] = e;
      }
    }
  }
  // cerr << "D : ";
  // for(auto d : D) cerr << d << " ";
  // cerr << endl;
  for(int i = 1; i < 20; ++i){
    for(int j = 0; j < N; ++j){
      auto s = V[i-1][j];
      auto t = V[i-1][s.second];
      V[i][j] = {s.first+t.first,t.second};
    }
  }
  auto solve = [&](vector<int> X){
                 long long ret = 0;
                 set<int> S;
                 for(auto x : X) S.insert(x);
                 while(true){
                   int max_d = 0, min_d = 100;
                   for(auto v : S){
                     max_d = max(max_d, D[v]);
                     min_d = min(min_d, D[v]);
                   }
                   if(max_d == min_d) break;
                   set<int> S_;
                   for(auto v : S){
                     if(D[v] < max_d){
                       S_.insert(v);
                       continue;
                     }
                     ret += V[0][v].first;
                     S_.insert(V[0][v].second);
                   }
                   S = S_;
                 }
                 while(S.size() > 1){
                   for(int k = 19; k >= 0; --k){
                     set<int> S_;
                     for(auto v : S){
                       S_.insert(V[k][v].second);
                     }
                     if(S_.size() == S.size()){
                       for(auto v : S){
                         ret += V[k][v].first;
                       }
                       swap(S,S_);
                     }
                     // if(V[k][u].second != V[k][v].second){
                     //   ret += V[k][u].first + V[k][v].first;
                     //   u = V[k][u].second;
                     //   v = V[k][v].second;
                     // }
                   }
                   set<int> S_;
                   for(auto v : S){
                     ret += V[0][v].first;
                     S_.insert(V[0][v].second);
                   }
                   swap(S,S_);
                 }
                 return ret;
               };
  int Q;
  cin >> Q;
  while(Q--){
    int k;
    cin >> k;
    vector<int> X(k);
    for(int i = 0; i < k; ++i) cin >> X[i];
    // auto p = solve(X[0],X[1]);
    // auto q = solve(X[1],X[2]);
    // auto r = solve(X[2],X[0]);
    // auto s = solve(q.second,X[0]);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[1],p.first,p.second);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[2],r.first,r.second);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],q.second,s.first,s.second);
    // long long ans = p.first + r.first - s.first;
    long long ans = solve(X);
    cout << ans << endl;
  }
}
0