제출 #963191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963191		phamducminh	Sjekira (COCI20_sjekira)	C++17	110 / 110	45 ms	11216 KiB

sjekira

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>




using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define endl "\n"
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD=998244353;
const int maxN=2e5+9;
const int LOG=31;

//------------------------


void solve();

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }

    cerr << "Time: " << TIME << "s.\n";
    cerr << "ducminh";
    return 0;
}

/// -------------- PROBLEM SOLUION --------------------


struct minh{
    long long u,v,w;
};
long long n,cost[200009];
vector<minh> ds;

bool cmp(minh a, minh b){
    return a.w<b.w;
}

long long truoc[200009], rnk[200009];

void init(){

    for (long long i=0; i<=n; i++){
        truoc[i]=i; rnk[i]=1;
    }
}

long long root(long long u){
    if (truoc[u]==u) return u;

    return truoc[u]=root(truoc[u]);
}

long long hop(long long u, long long v){
    u=root(u); v=root(v);

    if (u==v) return 0;

    long long ans=cost[u]+cost[v];

    if (rnk[u]<rnk[v]) swap(u,v);
    truoc[u]=v;
    rnk[u]+=rnk[v];

    cost[u]=max(cost[u],cost[v]);
    cost[v]=max(cost[v],cost[u]);
    return ans;
}

void solve(){



    cin >> n;

    init();

    for (int i=1; i<=n; i++){
        cin >> cost[i];
    }

    for (int i=1; i<n; i++){
        int x,y;

        cin >> x >> y;

        ds.push_back({x,y,max(cost[x],cost[y])});
    }


    sort(all(ds),cmp);

    long long ans=0;
    for (minh x: ds){
        ans+=hop(x.u,x.v);
    }

    cout << ans;


}

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