#include <bits/stdc++.h>
using namespace std;
int parent[500005];//whatever max number of nodes + 5 (for 1-index)
vector<pair<int, pair<int, int > > >v;
int dist[500005];
int visited[500005];
vector<pair<int, int> >v1[500005];
void ufdsinit(int n) {
for(int i = 0;i<=n;i++)parent[i] = i; //each node is its own set
}
int findset(int a) {
if(parent[a] == a) return a; //we reached the head
else {
parent[a] = findset(parent[a]); //use recursion to go to the parent
return parent[a]; //path compression
}
}
void mergeset(int a,int b) {
int pa = findset(a);
int pb = findset(b);
if(pa!=pb) //if they are a different set
parent[pb] = pa; //merge them together
}
void dfs(int root, int mini){
if(visited[root] == 1)return;
visited[root] = 1;
for(int i=0;i<v1[root].size();i++){
int a = v1[root][i].first;
int b = v1[root][i].second;
mini = min(mini, b);
dist[a] = max(dist[a], mini);
dfs(a, mini);
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,e,q;
cin >> n >> e >> q;
for(int i=0;i<e;i++){
int a,b,c;
cin >> a >> b >> c;
v.push_back(make_pair(c, make_pair(a,b)));
}
ufdsinit(n);
sort(v.begin(), v.end());
for(int i=v.size()-1;i>=0;i--){
long long a = v[i].first;
int b = v[i].second.first;
int c = v[i].second.second;
if(findset(b) == findset(c))continue;
mergeset(b,c);
v1[b].push_back(make_pair(c, a));
v1[c].push_back(make_pair(b, a));
}
dfs(1, 1e9+5);
for(int i=0;i<q;i++){
int a;
cin >> a;
cout << dist[a] << "\n";
}
}
Compilation message
sightseeing.cpp: In function 'void dfs(int, int)':
sightseeing.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=0;i<v1[root].size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12224 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
15296 KB |
Output is correct |
| 2 |
Correct |
31 ms |
14908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1441 ms |
75056 KB |
Output is correct |
| 2 |
Correct |
2115 ms |
134236 KB |
Output is correct |
