제출 #1319502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319502		nathako9n	Sjekira (COCI20_sjekira)	C++20	110 / 110	32 ms	3104 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){
    int ma = max(ar[a.first], ar[a.second]);
    int mb = max(ar[b.first], ar[b.second]);
    return ma < mb;
}
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[hx]+mx[hy];
        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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60