Submission #1298278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298278		pera	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1494 ms	99020 KiB

sightseeing

#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';

}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10