Submission #897470

#	Time	Username	Problem	Language	Result	Execution time	Memory
897470		mihtriii295	Sjekira (COCI20_sjekira)	C++17	110 / 110	39 ms	5844 KiB

sjekira

#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define ll  long long
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define el  cout << '\n' 

using namespace std;

const ll N = 1e5 + 1;
const ll logN = 20;
const ll MOD = 1e9 + 7;

ll a[N], res, n;

struct edge{
    int u, v;
};
vector<edge> adj;

bool cmp(edge x, edge y){
    return max(a[x.u], a[x.v]) < max(a[y.u], a[y.v]);
}

struct DSU{
    ll par[N], sz[N];
    void init(ll n){
        for (ll i = 1; i <= n; ++i){
            sz[i] = 1;
            par[i] = i;
        }
    }

    ll Find(ll u){
        if (u == par[u]) return u;
        return par[u] = Find(par[u]);
    }

    ll Union(ll u, ll v){
        u = Find(u);
        v = Find(v);
        if (u == v) return 0;
        ll res = a[u] + a[v];
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        a[u] = max(a[u], a[v]);
        a[v] = max(a[u], a[v]);
        return res;
    }
} dsu;

int main(){
    if(fopen("coci2021_r2_sjekira.inp", "r")){
        freopen("coci2021_r2_sjekira.inp", "r", stdin);
        freopen("coci2021_r2_sjekira.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj.push_back({u, v});
    }
    dsu.init(n);
    sort(begin(adj), end(adj), cmp);
    for (edge x : adj){
        res += dsu.Union(x.u, x.v);
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("coci2021_r2_sjekira.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sjekira.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("coci2021_r2_sjekira.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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