#include <bits/stdc++.h>
using namespace std;
//#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e6 + 69;
//vector <pair<int, int>> adj[maxn];
int d[maxn];
int sz[maxn];
int root[maxn];
vector <int> st[maxn];
int ans[maxn];
//set <int> st[maxn];
//const int maxn = 5e5 + 69;
int findroot(int x)
{
while (x!=root[x])
x = root[x];
return x;
}
void unite(int x, int y)
{
//x = findroot(x);
//y = findroot(y);
if (x==y)
return;
if (sz[x]<sz[y])
swap(x, y);
sz[x] += sz[y];
root[y] = x;
for (int i=0; i<st[y].size(); i++)
st[x].push_back(st[y][i]);
}
void Solve()
{
int v, e, q;
cin>>v>>e>>q;
vector <pair<int, pair<int, int>>> edg;
for (int i=0; i<e; i++)
{
int a, b, c;
cin>>a>>b>>c;
a--;
b--;
//adj[a].push_back(make_pair(b,c));
//adj[b].push_back(make_pair(a, c));
edg.push_back(make_pair(c, make_pair(a, b)));
}
sort(edg.begin(), edg.end(), greater<pair<int, pair<int, int>>>());
for (int i=0; i<v; i++)
{
sz[i] = 1;
root[i] = i;
st[i].push_back(i);
}
for (int i=0; i<e; i++)
{
int u = edg[i].second.first;
int v = edg[i].second.second;
//cout<<edg[i].first<<"\n";
u = findroot(u);
v = findroot(v);
if (v==findroot(0))
{
swap(u, v);
}
if (u==findroot(0) && v!=findroot(0))
{
//cout<<"YES "<<i+1<<" "<<v+1<<"\n";
for (int j=0; j<(int)(st[v].size()); j++)
{
//cout<<"UPDATED "<<st[v][j] + 1<<" "<<edg[i].first<<"\n";
ans[st[v][j]] = edg[i].first;
}
}
unite(u, v);
//cout<<"PRINTING\n";
//for (int j=0; j<n; j++)
//{
//}
}
for (int i=0; i<q; i++)
{
int x;
cin>>x;
x--;
cout<<ans[x]<<"\n";
}
}
int32_t main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
sightseeing.cpp: In function 'void unite(int, int)':
sightseeing.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i=0; i<st[y].size(); i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
117748 KB |
Output is correct |
| 2 |
Correct |
64 ms |
117708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
117840 KB |
Output is correct |
| 2 |
Correct |
58 ms |
117792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
121408 KB |
Output is correct |
| 2 |
Correct |
82 ms |
120832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1556 ms |
233604 KB |
Output is correct |
| 2 |
Correct |
2053 ms |
252372 KB |
Output is correct |
