Submission #948998

#TimeUsernameProblemLanguageResultExecution timeMemory
948998IrateSightseeing (NOI14_sightseeing)C++17
4 / 25
1223 ms107916 KiB
#include <bits/stdc++.h> using namespace std; const int mxM = 5e6 + 6; const int mxN = 5e5 + 5; struct Edge{ int u, v, w; bool operator<(Edge &other){ return w > other.w; } }; struct DSU{ vector<int>par; vector<set<int>>s; DSU(int n){ par.assign(n + 1, -1); s.resize(n + 1); for(int i = 1;i <= n;++i){ s[i].insert(i); } } int FindRep(int u){ if(par[u] < 0)return u; return par[u] = FindRep(par[u]); } void Union(int u, int v){ u = FindRep(u); v = FindRep(v); if(u == v)return; if(par[u] > par[v])swap(u, v); for(auto i : s[v])s[u].insert(i); par[u] += par[v]; par[v] = u; } }; Edge edges[mxM]; int ans[mxN]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; for(int i = 0;i < m;++i){ int u, v, w; cin >> u >> v >> w; edges[i] = {u, v, w}; } DSU dsu(n); sort(edges, edges + m); for(int i = 0;i < n;++i){ int u = edges[i].u, v = edges[i].v, w = edges[i].w; u = dsu.FindRep(u); v = dsu.FindRep(v); int node = dsu.FindRep(1); if((u == node && v == node) || (u != node && v != node)){ dsu.Union(u, v); } else{ if(u == node){ for(auto i : dsu.s[v])ans[i] = w; } else{ for(auto i : dsu.s[u])ans[i] = w; } dsu.Union(u, v); } } while(q--){ int node; cin >> node; cout << ans[node] << '\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...