oj.uz

답안 #374303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374303 2021-03-07T07:26:16 Z kartel Sjekira (COCI20_sjekira) C++14
110 / 110
 94 ms 8928 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 1e5 + 500;

int pr[N], mx[N], siz[N];
int n, cost[N], num[N];
vector <int> g[N];
ll ans;
bool mk[N];

int f(int x) {return (x == pr[x] ? x : pr[x] = f(pr[x]));}

void link(int x, int y) {
    x = f(x);
    y = f(y);

    if (siz[x] > siz[y]) {
        swap(x, y);
    }
    mx[y] = max(mx[x], mx[y]);
    pr[x] = y;
    siz[y] += siz[x];
}

bool cmp(int _i, int _j) {return (cost[_i] > cost[_j]);}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        num[i] = i;
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].pb(v);
        g[v].pb(u);
    }

    sort(arr_all(num, n), cmp);

    vector <pii> vc;

    for (int i = 1; i <= n; i++) {
        int v = num[i];
        for (auto u : g[v]) {
            if (mk[u])
                continue;

            vc.pb({u, v});
        }
        mk[v] = 1;
    }

    reverse(all(vc));

    for (int i = 1; i <= n; i++) {
        pr[i] = i;
        siz[i] = 1;
        mx[i] = cost[i];
    }

    for (auto pi : vc) {
        int v = pi.F;
        int u = pi.S;

        if (f(v) == f(u)) {
            continue;
        }

        if (cost[v] < cost[u]) {
            swap(u, v);
        }

        ans += cost[v];
        ans += mx[f(u)];

        link(v, u);
    }

    cout << ans;
}


/*

7
4 6 7 2 3 1 5
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7656 KB Output is correct
2 Correct 49 ms 6500 KB Output is correct
3 Correct 47 ms 6376 KB Output is correct
4 Correct 43 ms 6888 KB Output is correct
5 Correct 68 ms 8800 KB Output is correct
6 Correct 51 ms 8800 KB Output is correct
7 Correct 52 ms 8032 KB Output is correct
8 Correct 45 ms 7520 KB Output is correct
9 Correct 32 ms 5864 KB Output is correct
10 Correct 57 ms 8800 KB Output is correct

Subtask #3
30.0 / 30.0

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

Subtask #4
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 53 ms 7656 KB Output is correct
7 Correct 49 ms 6500 KB Output is correct
8 Correct 47 ms 6376 KB Output is correct
9 Correct 43 ms 6888 KB Output is correct
10 Correct 68 ms 8800 KB Output is correct
11 Correct 51 ms 8800 KB Output is correct
12 Correct 52 ms 8032 KB Output is correct
13 Correct 45 ms 7520 KB Output is correct
14 Correct 32 ms 5864 KB Output is correct
15 Correct 57 ms 8800 KB Output is correct
16 Correct 3 ms 2796 KB Output is correct
17 Correct 4 ms 2796 KB Output is correct
18 Correct 2 ms 2796 KB Output is correct
19 Correct 3 ms 2796 KB Output is correct
20 Correct 3 ms 2796 KB Output is correct
21 Correct 17 ms 4200 KB Output is correct
22 Correct 14 ms 4080 KB Output is correct
23 Correct 73 ms 8800 KB Output is correct
24 Correct 67 ms 7008 KB Output is correct
25 Correct 50 ms 6880 KB Output is correct
26 Correct 32 ms 5608 KB Output is correct
27 Correct 37 ms 6120 KB Output is correct
28 Correct 55 ms 7396 KB Output is correct
29 Correct 36 ms 5864 KB Output is correct
30 Correct 94 ms 8928 KB Output is correct