oj.uz

Submission #496115

# Submission time Handle Problem Language Result Execution time Memory
496115 2021-12-20T17:39:10 Z AlperenT Sjekira (COCI20_sjekira) C++17
0 / 110
 51 ms 8652 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 8652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -