제출 #1298278

#제출 시각아이디문제언어결과실행 시간메모리
1298278peraSightseeing (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...