Submission #793082

#	Time	Username	Problem	Language	Result	Execution time	Memory
793082		1075508020060209tc	Sjekira (COCI20_sjekira)	C++14	110 / 110	78 ms	7760 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ar[500005];
int uf[500005];
int umx[500005];

int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
umx[pb]=max(umx[pa],umx[pb]);
}

struct edge{
int a;int b;int v;
bool operator<(const edge &ee)const{
    if(v>ee.v){return 1;}
    return 0;
}
}e[500005];
signed main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        uf[i]=i;
        umx[i]=ar[i];
    }
    for(int i=1;i<=n-1;i++){
        cin>>e[i].a>>e[i].b;
        e[i].v=max(ar[e[i].a],ar[e[i].b]);
    }
    sort(e+1,e+n);
    reverse(e+1,e+n);
    int ans=0;
    for(int i=1;i<=n-1;i++){
        int a;int b;
        a=e[i].a;b=e[i].b;
        ans+=umx[fin(a)]+umx[fin(b)];
        mrg(a,b);
    }
    cout<<ans<<endl;

    return 0;
}

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