제출 #1357042

#제출 시각아이디문제언어결과실행 시간메모리
1357042alexddSecurity Guard (JOI23_guard)C++20
50 / 100
144 ms33992 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
vector<int> con[200005], arb[200005];
int s[200005];

namespace DSU
{
    int father[200005], siz[200005], strongest[200005];
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            father[i] = i;
            siz[i] = 1;
            strongest[i] = i;
        }
    }
    int get(int x)
    {
        if(father[x] != x)
            father[x] = get(father[x]);
        return father[x];
    }
    void unite(int x, int y)
    {
        x = get(x);
        y = get(y);
        if(x == y)
            return;
        if(siz[x] < siz[y])
            swap(x,y);
        siz[x] += siz[y];
        father[y] = x;
        if(s[strongest[y]] > s[strongest[x]])
            strongest[x] = strongest[y];
    }
}

bool cmp_s(int x, int y)
{
    return s[x] < s[y];
}

int get_mst(int q)
{
    vector<pair<int, pair<int,int>>> edges;
    for(int i=1;i<=n;i++)
    {
        for(int j:con[i])
        {
            if(j <= i)
                continue;
            edges.push_back({s[i] + s[j], {i, j}});
        }
    }
    sort(edges.begin(), edges.end());

    int sum = 0;
    DSU::init();
    for(auto [c,e]:edges)
    {
        if(DSU::get(e.first) != DSU::get(e.second))
        {
            DSU::unite(e.first, e.second);
            sum += c;
        }
    }
    return sum;
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        cin>>s[i];

    int u,v;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }

    int rez = get_mst(q);

    int maxs = 0;
    for(int u=1;u<=n;u++)
    {
        maxs = max(maxs, s[u]);
        rez -= s[u];
    }
    rez += maxs;

    cout<<rez;

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…