oj.uz

답안 #854608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854608 2023-09-28T06:57:47 Z vjudge1 Sjekira (COCI20_sjekira) C++17
110 / 110
 43 ms 8028 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct DSU {
    int n;
    vector <int> par;
    vector <int> vals;

    DSU(int n) : n(n) {
        par.resize(n +5);
        vals.resize(n +5);
        iota(par.begin(), par.end(), 0ll);
    } 

    inline void build(vector <int> &vec) {
        for(int i = 1; i <= n; i++) {
            vals[i] = vec[i];
        }
    }

    inline int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }

    inline bool same(int a, int b) {
        return get(a) == get(b);
    }

    inline bool unite(int a, int b) {
        if(same(a, b))
            return false;

        a = get(a);
        b = get(b);

        par[a] = b;
        vals[b] = max(vals[b], vals[a]);

        return true;
    }

    inline int val(int a) {
        return vals[get(a)];
    }
};

#define ONLINE_JUDGE
void solve() {
    int n;
    cin >> n;

    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];

    vector <int> adj[n +1];
    for(int i = 1; i <= n -1; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    DSU dsu(n);
    dsu.build(vec);

    vector <int> inds(n +1);
    iota(inds.begin(), inds.end(), 0ll);
    sort(inds.begin(), inds.end(), [&](int a, int b) -> bool {
        return vec[a] < vec[b];
    });

    vector <bool> activated(n +5, false);

    i64 res = 0;
    for(int i = 1; i <= n; i++) {
        int node = inds[i];
        activated[node] = true;
        int mx = dsu.val(node);
        for(int &child : adj[node]) {
            if(activated[child]) {
                res += 0LL + mx + dsu.val(child);
                dsu.unite(child, node);
            }
        }
    }

    cout << res << "\n";
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

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

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 5968 KB Output is correct
2 Correct 25 ms 4804 KB Output is correct
3 Correct 27 ms 4444 KB Output is correct
4 Correct 27 ms 4940 KB Output is correct
5 Correct 40 ms 7320 KB Output is correct
6 Correct 30 ms 8028 KB Output is correct
7 Correct 26 ms 6740 KB Output is correct
8 Correct 24 ms 6236 KB Output is correct
9 Correct 16 ms 4384 KB Output is correct
10 Correct 30 ms 7772 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 32 ms 5968 KB Output is correct
7 Correct 25 ms 4804 KB Output is correct
8 Correct 27 ms 4444 KB Output is correct
9 Correct 27 ms 4940 KB Output is correct
10 Correct 40 ms 7320 KB Output is correct
11 Correct 30 ms 8028 KB Output is correct
12 Correct 26 ms 6740 KB Output is correct
13 Correct 24 ms 6236 KB Output is correct
14 Correct 16 ms 4384 KB Output is correct
15 Correct 30 ms 7772 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 10 ms 2004 KB Output is correct
22 Correct 8 ms 1628 KB Output is correct
23 Correct 40 ms 7272 KB Output is correct
24 Correct 30 ms 5176 KB Output is correct
25 Correct 28 ms 5140 KB Output is correct
26 Correct 19 ms 3420 KB Output is correct
27 Correct 22 ms 4188 KB Output is correct
28 Correct 30 ms 5652 KB Output is correct
29 Correct 22 ms 3936 KB Output is correct
30 Correct 43 ms 7508 KB Output is correct