#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
// #define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
struct edge
{
int u, v, q;
bool operator< (edge other){
return mp(q, mp(u, v)) < mp(other.q, mp(other.u, other.v));
}
};
int V, E, Q;
vector<edge> edgelist;
vector<vector<pair<int, int> > > graph;
vector<int> uf, dist;
int root(int a){
if(uf[a] == a) return a;
return uf[a] = root(uf[a]);
}
void merge(int a, int b){
a = root(a); b = root(b);
if(rand()%2) swap(a, b);
uf[a] = b;
}
void dfs(int u, int par, int d){
dist[u] = d;
for(auto e : graph[u]) if(e.first!=par){
dfs(e.first, u, min(d,e.second));
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>V>>E>>Q;
edgelist.resize(E);
uf.resize(V);
graph.resize(V);
dist.resize(V);
F(i,E){
int a, b, q;
cin>>a>>b>>q;
edgelist[i] = {a-1, b-1, q};
}
sort(edgelist.begin(), edgelist.end());
F(i,V) uf[i] = i;
for(int i = E-1; i>=0; i--){
H(i);
edge e = edgelist[i];
if(root(e.u)!=root(e.v)){
merge(e.u, e.v);
graph[e.u].push_back({e.v, e.q});
graph[e.v].push_back({e.u, e.q});
}
}
dfs(0, -1, 1e18);
F(i, Q){
int a;
cin>>a;
cout<<dist[a-1]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
4856 KB |
Output is correct |
| 2 |
Correct |
36 ms |
4600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2255 ms |
106108 KB |
Output is correct |
| 2 |
Correct |
3098 ms |
262144 KB |
Output is correct |
