Submission #958016

#TimeUsernameProblemLanguageResultExecution timeMemory
958016kimSecurity Guard (JOI23_guard)C++17
37 / 100
156 ms19528 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...