oj.uz

Submission #496117

# Submission time Handle Problem Language Result Execution time Memory
496117 2021-12-20T17:51:54 Z AlperenT Sjekira (COCI20_sjekira) C++17
110 / 110
 72 ms 11136 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];

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3452 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8080 KB Output is correct
2 Correct 34 ms 8072 KB Output is correct
3 Correct 28 ms 7880 KB Output is correct
4 Correct 32 ms 8888 KB Output is correct
5 Correct 47 ms 11112 KB Output is correct
6 Correct 46 ms 11092 KB Output is correct
7 Correct 38 ms 10188 KB Output is correct
8 Correct 31 ms 9760 KB Output is correct
9 Correct 22 ms 7372 KB Output is correct
10 Correct 46 ms 10992 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3452 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 4 ms 3536 KB Output is correct
7 Correct 2 ms 3536 KB Output is correct
8 Correct 3 ms 3468 KB Output is correct
9 Correct 2 ms 3488 KB Output is correct
10 Correct 2 ms 3540 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3452 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 40 ms 8080 KB Output is correct
7 Correct 34 ms 8072 KB Output is correct
8 Correct 28 ms 7880 KB Output is correct
9 Correct 32 ms 8888 KB Output is correct
10 Correct 47 ms 11112 KB Output is correct
11 Correct 46 ms 11092 KB Output is correct
12 Correct 38 ms 10188 KB Output is correct
13 Correct 31 ms 9760 KB Output is correct
14 Correct 22 ms 7372 KB Output is correct
15 Correct 46 ms 10992 KB Output is correct
16 Correct 4 ms 3536 KB Output is correct
17 Correct 2 ms 3536 KB Output is correct
18 Correct 3 ms 3468 KB Output is correct
19 Correct 2 ms 3488 KB Output is correct
20 Correct 2 ms 3540 KB Output is correct
21 Correct 12 ms 5320 KB Output is correct
22 Correct 14 ms 5072 KB Output is correct
23 Correct 72 ms 10800 KB Output is correct
24 Correct 37 ms 9008 KB Output is correct
25 Correct 40 ms 9024 KB Output is correct
26 Correct 32 ms 7024 KB Output is correct
27 Correct 31 ms 7632 KB Output is correct
28 Correct 42 ms 8992 KB Output is correct
29 Correct 26 ms 6992 KB Output is correct
30 Correct 54 ms 11136 KB Output is correct