Submission #155954

#TimeUsernameProblemLanguageResultExecution timeMemory
155954MinnakhmetovSightseeing (NOI14_sightseeing)C++14
25 / 25
2719 ms197692 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; struct E { int a, b, w; }; const int N = 5e5 + 5; int w[N], ans[N]; bool bg[N]; vector<E> v; vector<int> qr[N]; int findSet(int a) { return w[a] < 0 ? a : w[a] = findSet(w[a]); } void connect(int a, int b, int c) { a = findSet(a); b = findSet(b); if (a == b) return; if (w[a] > w[b]) swap(a, b); qr[a].insert(qr[a].end(), all(qr[b])); w[a] += w[b]; w[b] = a; if (bg[a] || bg[b]) { bg[a] = 1; for (int x : qr[a]) ans[x] = c; qr[a].clear(); } } signed 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 a, b, c; cin >> a >> b >> c; a--, b--; v.push_back({a, b, c}); } sort(all(v), [](E a, E b) { return a.w > b.w; }); fill(w, w + n, -1); bg[0] = 1; for (int i = 0; i < q; i++) { int x; cin >> x; qr[x - 1].push_back(i); } for (E e : v) { connect(e.a, e.b, e.w); } for (int i = 0; i < q; i++) { cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...