This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
vector<int> adj[200005];
int a[200005];
struct A{
int u,v;
A(int u=0,int v=0):u(u),v(v){}
bool operator<(const A &o)const{
if(a[u]!=a[o.u]) return a[u]>a[o.u];
return a[v]>a[o.u];
}
};
priority_queue<A> pq;
ll dp[200005];
bitset<200005> vis;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n,m,Q; cin>>n>>m>>Q;
int mx=1;
for(int i=1;i<=n;++i){
cin>>a[i];
if(a[i]>a[mx]) mx=i;
dp[i]=1e18;
}
for(int i=0;i<m;++i){
int u,v; cin>>u>>v;
adj[u].eb(v), adj[v].eb(u);
}
for(auto &v:adj[mx]){
dp[v]=a[mx];
pq.emplace(mx,v);
}
dp[mx]=0;
vis[mx]=1;
while(pq.size()){
auto [p,u]=pq.top(); pq.pop();
if(dp[u]!=a[p]) continue;
vis[u]=1;
for(auto &v:adj[u]){
if(dp[v]<=a[u]||vis[v]) continue;
dp[v]=a[u];
pq.emplace(u,v);
}
}
ll ans=0;
for(int i=1;i<=n;++i) ans+=dp[i];
cout<<ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |