#include <bits/stdc++.h>
using namespace std;
//actual solution is at bottom//
////<pbds>////
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
// change null_type for map
// change less to less_equal for multiset
#define ook order_of_key
#define fbo find_by_order*/
///</pbds>///
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define google(i) cout<<"Case #"<<i<<" :";
///<constants>///
const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
///</constants>///
///<IO>///
namespace io {
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
// cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
}
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace io;
///</IO>///
///<execution-time>///
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
/*example for clock usage
clock_t z = clock();
debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
*/
///</execution-time>///
struct UFDS {
int n, c;
vector<int> len, par;
void init(int x, int y = 1) {
n = x;
c = y;
par.resize(n+2);
len.assign(n+2, 1);
iota(par.begin(), par.end(), 0);
}
int fin(int v) { return par[v] == v ? v : par[v] = fin(par[v]); }
bool join(int a, int b) {
a = fin(a); b = fin(b);
if(a == b) return false;
if(rng() % 2) swap(a, b);
if(c && len[a] < len[b])
swap(a, b);
par[b] = a;
if(c) len[a] += len[b];
return true;
}
int szz(int x) { return len[fin(x)]; }
};
int n, m, q;
vector<vector<pair<int,int>>> mst;
vector<pair<int,pair<int,int>>> initial;
vector<int> ans;
void init(){
cin>>n>>m>>q;
mst.resize(n+2);
ans.resize(n+1);
ans.assign(sizeof(ans),INF);
for(int i = 0; i < m ; ++i){
int u, v, w;
cin>> u >> v >> w;
initial.push_back({ w , {u , v} });
}
sort( initial.begin(), initial.end() ,greater<pair<int,pair<int,int>>>());
}
void kruskal(){
UFDS dsu;
dsu.init(n);
for(auto a: initial){
int weight = a.first;
int from = a.second.first;
int to= a.second.second;
if( dsu.join(from,to) ){
mst[from].push_back({weight,to});
mst[to].push_back({weight,from});
}
}
}
void dfs(int u,int par,int mxx){
ans[u]=min( ans[u] , mxx);
for(auto i:mst[u]){
if( i.second != par)
dfs(i.second, u , min( i.first , mxx));
}
}
void query(){
while(q--){
int xx;
cin >> xx;
cout << ans[xx] << "\n";
}
}
signed main(){
setIO("");
init();
kruskal();
dfs(1,-1,INF);
query();
return 0;
}
/* stuff you should look for
* check whether you have read the problem correctly
* int overflow, array bounds
* special cases (n=1?), slow multiset operations
* do smth instead of nothing and stay organized
*/
Compilation message
sightseeing.cpp: In function 'void io::setIn(std::string)':
sightseeing.cpp:34:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
34 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp: In function 'void io::setOut(std::string)':
sightseeing.cpp:35:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
35 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
5088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1806 ms |
110448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
