Submission #958016

#	Time	Username	Problem	Language	Result	Execution time	Memory
958016		kim	Security Guard (JOI23_guard)	C++17	37 / 100	156 ms	19528 KiB

guard

#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;
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 13
• Subtask 5: 0 / 8
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24