oj.uz

Submission #963191

# Submission time Handle Problem Language Result Execution time Memory
963191 2024-04-14T16:50:54 Z phamducminh Sjekira (COCI20_sjekira) C++17
110 / 110
 45 ms 11216 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>




using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define endl "\n"
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD=998244353;
const int maxN=2e5+9;
const int LOG=31;

//------------------------


void solve();

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


    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }

    cerr << "Time: " << TIME << "s.\n";
    cerr << "ducminh";
    return 0;
}

/// -------------- PROBLEM SOLUION --------------------


struct minh{
    long long u,v,w;
};
long long n,cost[200009];
vector<minh> ds;

bool cmp(minh a, minh b){
    return a.w<b.w;
}

long long truoc[200009], rnk[200009];

void init(){

    for (long long i=0; i<=n; i++){
        truoc[i]=i; rnk[i]=1;
    }
}

long long root(long long u){
    if (truoc[u]==u) return u;

    return truoc[u]=root(truoc[u]);
}

long long hop(long long u, long long v){
    u=root(u); v=root(v);

    if (u==v) return 0;

    long long ans=cost[u]+cost[v];

    if (rnk[u]<rnk[v]) swap(u,v);
    truoc[u]=v;
    rnk[u]+=rnk[v];

    cost[u]=max(cost[u],cost[v]);
    cost[v]=max(cost[v],cost[u]);
    return ans;
}

void solve(){



    cin >> n;

    init();

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

    for (int i=1; i<n; i++){
        int x,y;

        cin >> x >> y;

        ds.push_back({x,y,max(cost[x],cost[y])});
    }


    sort(all(ds),cmp);

    long long ans=0;
    for (minh x: ds){
        ans+=hop(x.u,x.v);
    }

    cout << ans;


}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9680 KB Output is correct
2 Correct 22 ms 7628 KB Output is correct
3 Correct 26 ms 7380 KB Output is correct
4 Correct 23 ms 9296 KB Output is correct
5 Correct 33 ms 9680 KB Output is correct
6 Correct 39 ms 11216 KB Output is correct
7 Correct 35 ms 10704 KB Output is correct
8 Correct 34 ms 9420 KB Output is correct
9 Correct 20 ms 7276 KB Output is correct
10 Correct 41 ms 9688 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4584 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 28 ms 9680 KB Output is correct
7 Correct 22 ms 7628 KB Output is correct
8 Correct 26 ms 7380 KB Output is correct
9 Correct 23 ms 9296 KB Output is correct
10 Correct 33 ms 9680 KB Output is correct
11 Correct 39 ms 11216 KB Output is correct
12 Correct 35 ms 10704 KB Output is correct
13 Correct 34 ms 9420 KB Output is correct
14 Correct 20 ms 7276 KB Output is correct
15 Correct 41 ms 9688 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4584 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 8 ms 5976 KB Output is correct
22 Correct 8 ms 5976 KB Output is correct
23 Correct 45 ms 9664 KB Output is correct
24 Correct 25 ms 9164 KB Output is correct
25 Correct 25 ms 9164 KB Output is correct
26 Correct 20 ms 7120 KB Output is correct
27 Correct 19 ms 7376 KB Output is correct
28 Correct 24 ms 8844 KB Output is correct
29 Correct 18 ms 7124 KB Output is correct
30 Correct 38 ms 9776 KB Output is correct