제출 #1298278

#제출 시각아이디문제언어결과실행 시간메모리
1298278pera관광 (NOI14_sightseeing)C++20
25 / 25
1494 ms99020 KiB
#include<bits/stdc++.h>
using namespace std;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n , m , Q;
   cin >> n >> m >> Q;
   vector<tuple<int , int , int>> e;
   for(int i = 0;i < m;i ++){
      int u , v , w;
      cin >> u >> v >> w;
      e.emplace_back(w , u , v);
   }

   vector<int> ans(n + 1 , -1) , P(n + 1);
   vector<vector<int>> G(n + 1);
   iota(P.begin() , P.end() , 0);
   for(int i = 1;i <= n;i ++){
      G[i] = {i};
   }

   function<int(int)> find = [&](int u){
      return P[u] == u ? u : P[u] = find(P[u]);
   };

   sort(e.rbegin() , e.rend());

   auto join = [&](int u , int v){
      u = find(u);
      v = find(v);
      if((int)G[u].size() < (int)G[v].size()){
         swap(u , v);
      }
      for(int x : G[v]){
         G[u].emplace_back(x);
      }
      vector<int>().swap(G[v]);
      P[v] = u;
   };


   for(auto [w , u , v] : e){

      if(find(u) == find(v)){
         continue;
      }

      if(find(1) != find(u)){
         swap(u , v);
      }

      if(find(1) == find(u)){
         for(int x : G[find(v)]){
            ans[x] = w;
         }
      }

      join(u , v);
   }

   for(int i = 1;i <= Q;i ++){
      int x;
      cin >> x;
      cout << ans[x] << " ";
   }
   cout << '\n';

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...