# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1091652 | raphaelp | Sightseeing (NOI14_sightseeing) | C++14 | 2133 ms | 82392 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }
int main()
{
int N, M, Q;
cin >> N >> M >> Q;
vector<vector<pair<int, int>>> buckets(1000010);
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--, b--;
buckets[c].push_back({a, b});
}
p.assign(N, 0);
for (int i = 0; i < N; i++)
p[i] = i;
vector<int> dist(N);
vector<vector<int>> contains(N);
for (int i = 0; i < N; i++)
contains[i].push_back(i);
for (int i = 1000000; i >= 0; i--)
{
for (int j = 0; j < buckets[i].size(); j++)
{
if (M > 1000000)
continue;
int x = find(buckets[i][j].first), y = find(buckets[i][j].second);
if (x == y)
continue;
if (contains[x].size() > contains[y].size())
swap(x, y);
if (find(0) == x)
swap(x, y);
p[x] = y;
for (auto val : contains[x])
{
if (y == find(0))
dist[val] = i;
contains[y].push_back(val);
}
}
}
for (int i = 0; i < Q; i++)
{
int x;
cin >> x;
cout << dist[x - 1] << '\n';
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |