Submission #1069044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069044		LeeQuoMing	Sjekira (COCI20_sjekira)	C++14	110 / 110	38 ms	4828 KiB

sjekira

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) x.begin(),x.end()
#define FOR(i,sta, en, plus) for(int i = sta; i<=en; i+=plus)

using pii = pair<int,int>;
#define F first
#define S second
#define MP make_pair

#define dbg_time() cerr<<"Time: "<<1000 * ((double)clock() / (double)CLOCKS_PER_SEC) <<"ms"<<endl;

#define endl '\n';
const ll MOD = (ll)1e9+7;
const int M = 1e5+5;

ll ans =0;
int c[M];
vector<pair<int,int>> edge;

class DSU{
    private:
        vector<int> par, sz;
    public:
        DSU(int n): par(n+5), sz(n+5,1){                // init
            for(int i = 1; i<=n; ++i) par[i] = i;
        }
        int find(int x){
            return (par[x] == x ? x : par[x] = find(par[x]));
        }
        bool same(int a, int b){
            return find(a) == find(b);
        }
        bool unite(int a, int b){
            int u = find(a), v = find(b);
            if(u==v) return 0;
            ans += c[u] + c[v];
            c[u] = max(c[u], c[v]);
            par[v] = u;
            return 1;
        }
        int findsz(int u){
            return sz[find(u)];
        }
};

int main(){
    fast;
    int n; cin>>n;
    for(int i = 1; i<=n; ++i) cin>>c[i];
    DSU dsu(n);
    for(int i = 1,a,b; i<n; ++i){
        cin>>a>>b;
        edge.pb({a, b});
    }
    sort(all(edge), [&](pii a, pii b){
        return max(c[a.F],c[a.S]) < max(c[b.F],c[b.S]);
    });

    for(auto& p : edge){
        dsu.unite(p.F, p.S);
    }
    cout<<ans;
    // dbg_time();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60