Submission #529019

#	Time	Username	Problem	Language	Result	Execution time	Memory
529019		beepbeepsheep	Sjekira (COCI20_sjekira)	C++17	110 / 110	99 ms	16532 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
//#define endl '\n'
const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=1e5+5;
ll par[maxn];
multiset<ii> adj[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;
ll arr[maxn];
ll root(ll x){
    if (par[x]==x) return x;
    return par[x]=root(par[x]);
}
void connect(ll a, ll b){
    ll pa=root(a),pb=root(b);
    if (pa==pb) return;
    par[pa]=pb;
    if (adj[pa].size()>adj[pb].size()) swap(adj[pa],adj[pb]);
    for (auto u:adj[pa]) adj[pb].emplace(u);
    adj[pa].clear();
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,ele,a,b;
    cin>>n;
    for (int i=0;i<n;i++){
        par[i+1]=i+1;
        cin>>ele;
        arr[i+1]=ele;
        pq.emplace(ele,i+1);
    }
    for (int i=0;i<n-1;i++){
        cin>>a>>b;
        if (arr[a]>arr[b] || (arr[a]==arr[b] && a>b)) swap(a,b);
        adj[a].emplace(arr[b],b);
    }
    ll ans=0,c;
    while (pq.size()!=1){
        a=pq.top().first;
        b=pq.top().second;
        pq.pop();
        ans+=a+(adj[b].begin()->first);
        c=adj[b].begin()->second;
        adj[b].erase(adj[b].begin());
        connect(b,c);
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60