Submission #1319492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319492		nathako9n	Sjekira (COCI20_sjekira)	C++20	0 / 110	24 ms	2444 KiB

sjekira

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5+5;
int ar[N+3],n,he[N+2],mx[N+2];
vector<pair<int,int>>ed;
int fh(int x){
    if(x==he[x])return x;
    return he[x]=fh(he[x]);
}
void uh(int x,int y){
    x=fh(x); y=fh(y);
    if(x==y)return;
    he[x]=y;
    mx[x]=mx[y]=max(mx[x],mx[y]);
}
bool com(const pair<int,int>&a,const pair<int,int>&b){
    if(mx[a.first]==mx[b.first]){
        return mx[a.second]<=mx[b.second];
    }
    return mx[a.first]<=mx[b.first];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){cin>>ar[i];he[i]=i;mx[i]=ar[i];}
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        if(mx[x]>mx[y])swap(x,y);
        ed.push_back({x,y});
    }
    ll sum=0;

    sort(ed.begin(),ed.end(),com);

    for(auto [x,y]:ed){
       // cout<<x<<" "<<mx[x]<<" "<<y<<" "<<mx[y]<<endl;
        int hx=fh(x), hy=fh(y);
        if(hx==hy)continue;
        sum+=mx[x]+mx[y];
        uh(x,y);
    }
    cout<<sum;
}

/*

5
5 2 3 1 4
2 1
3 1
2 4
2 5

3
1 2 3
1 2
2 3

4
2 2 3 2
1 3
3 2
4 3

*/

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