#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int up=1e6+7;
const int mod=1e9+7;
const int inf=1e18+7;
const int ninf=(-1)*inf;
const int N=5e5+7;
/*
{
"cmd": ["g++.exe", "-std=c++14", "${file}",
"-o", "${file_base_name}.exe",
"&&", "${file_base_name}.exe<inputf.in>outputf.out"],
"shell":true,
"working_dir":"$file_path",
"selector":"source.cpp"
}
*/
/* user preference fix
"trim_automatic_white_space": false,
*/
vector <pii> adj[N];
vector <int> par(N),sz(N,1),ans(N);
vector <bool> vis(N,false);
int findroot(int a)
{
while(par[a]!=a)
a=par[a];
return a;
}
bool unite(int a,int b)
{
int x=a;
int y=b;
a=findroot(a);
b=findroot(b);
if(a==b)
{
return false;
}
if(sz[a]>sz[b])
swap(a,b);
par[a]=b;
sz[b]+=sz[a];
return true;
}
struct edge
{
int u,v,c;
};
bool cmp(edge a, edge b)
{
return a.c>b.c;
}
vector <int> res(N);
void dfs(int u ,int p,int c)
{
if(p==0 || p==1)
{
res[u]=c;
}
else
{
res[u]=min(c,res[p]);
}
//cout << u << " " << ans[u] << "\n";
for(auto it:adj[u])
{
if(it.ff==p)
{
continue;
}
dfs(it.ff,u,it.ss);
}
//cout << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << '\n';
}
void solve()
{
iota(par.begin(),par.end(),0);
//iota(p.begin(),p.end(),0);
int n,m,q;
cin>>n>>m>>q;
vector <edge> e(m);
for(int i=0;i<m;i++)
{
int u,v,c;
cin>>u>>v>>c;
//adj[u].push_back({v,c});
//adj[v].push_back({u,c});
e[i].u=u;
e[i].v=v;
e[i].c=c;
//cout << e[i].c << " ";
}
//cout << findroot(1) << '\n';
vector <int> ans(n+1);
sort(e.begin(),e.end(),cmp);
for(int i=0;i<m;i++)
{
int u=e[i].u;
int v=e[i].v;
int c=e[i].c;
int x=findroot(u);
int y=findroot(v);
//cout << x << " " << y << '\n';
if(unite(x,y))
{
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
}
/*
for(int i=1;i<=n;i++)
{
cout << i << ": ";
for(auto it:adj[i])
{
cout << it.ff << ' ';
}
cout << '\n';
}
*/
//ans[0]=0;
dfs(1,0,0);
//cout << ans[3] << '\n';
while(q--)
{
int x;
cin>>x;
//cout << x << '\n'
cout << res[x] << '\n';
//cout << ans[x] << '\n';
}
}
signed main(){
fast
solve();
}
Compilation message
sightseeing.cpp: In function 'bool unite(long long int, long long int)':
sightseeing.cpp:38:9: warning: unused variable 'x' [-Wunused-variable]
38 | int x=a;
| ^
sightseeing.cpp:39:9: warning: unused variable 'y' [-Wunused-variable]
39 | int y=b;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
27732 KB |
Output is correct |
| 2 |
Correct |
16 ms |
27748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
27936 KB |
Output is correct |
| 2 |
Correct |
13 ms |
27860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
31936 KB |
Output is correct |
| 2 |
Correct |
36 ms |
31404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1612 ms |
179928 KB |
Output is correct |
| 2 |
Correct |
2265 ms |
262144 KB |
Output is correct |
