제출 #1319495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319495		nathako9n	Sjekira (COCI20_sjekira)	C++20	110 / 110	32 ms	2928 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[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;
        ed.push_back({x,y});
    }
    ll sum=0;

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

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

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