Submission #328677

#	Time	Username	Problem	Language	Result	Execution time	Memory
328677		phathnv	Sjekira (COCI20_sjekira)	C++11	110 / 110	114 ms	2796 KiB

sjekira

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Sjekira"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;

struct DSU{
    int root[N], rnk[N], maxVal[N];
    void init(int n, int a[N]){
        for(int i = 1; i <= n; i++){
            root[i] = i;
            rnk[i] = 0;
            maxVal[i] = a[i];
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        root[u] = getRoot(root[u]);
        return root[u];
    }
    int unite(int u, int v){
        u = getRoot(u);
        v = getRoot(v);
        if (rnk[u] < rnk[v])
            swap(u, v);
        int res = maxVal[u] + maxVal[v];
        root[v] = u;
        rnk[u] += (rnk[u] == rnk[v]);
        maxVal[u] = max(maxVal[u], maxVal[v]);
        return res;
    }
} dsu;

int n, a[N];
ii eds[N];

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++)
        cin >> eds[i].X >> eds[i].Y;
}

void solve(){
    sort(eds + 1, eds + n, [&](const ii &ed1, const ii &ed2){
            return max(a[ed1.X], a[ed1.Y]) < max(a[ed2.X], a[ed2.Y]);
         });
    dsu.init(n, a);
    ll res = 0;
    for(int i = 1; i < n; i++)
        res += dsu.unite(eds[i].X, eds[i].Y);
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

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

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