제출 #496115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496115		AlperenT	Sjekira (COCI20_sjekira)	C++17	0 / 110	51 ms	8652 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];

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);

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

        vector<pair<int, int>> edges;

        for(auto e : graph[v]) edges.push_back({dsu.stmax[e], e});

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

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

    cout << ans;
}

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