제출 #496117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496117		AlperenT	Sjekira (COCI20_sjekira)	C++17	110 / 110	72 ms	11136 KiB

sjekira

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, v, a, b;

pair<int, int> arr[N];

long long ans;

vector<int> graph[N];

vector<pair<int, int>> edges;

bool vis[N];

struct DSU{
    int par[N], stsize[N], stmax[N];

    DSU(){
        for(int i = 1; i < N; i++) par[i] = i, stsize[i] = 1;
    }

    int setfind(int a){
        if(par[a] == a) return a;
        else return par[a] = setfind(par[a]);
    }

    int setunion(int a, int b){
        int sum = 0;

        a = setfind(a); b = setfind(b);

        if(a != b){
            sum = stmax[a] + stmax[b];

            if(stsize[b] > stsize[a]) swap(a, b);
            stsize[a] += stsize[b];
            par[b] = par[a];
            stmax[a] = max(stmax[a], stmax[b]);
        }
        
        return sum;
    }
};

DSU dsu;

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

    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> arr[i].first;
        arr[i].second = i;
    }

    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;

        graph[a].push_back(b); graph[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) dsu.stmax[i] = arr[i].first;

    sort(arr + 1, arr + n + 1, greater<pair<int, int>>());

    for(int i = 1; i <= n; i++){
        v = arr[i].second;

        for(auto e : graph[v]){
            if(!vis[e]) edges.push_back({v, e});
        }

        vis[v] = true;
    }

    reverse(edges.begin(), edges.end());

    for(auto e : edges) ans += dsu.setunion(e.first, e.second);

    cout << ans;
}

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