Submission #1287703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287703		shidou26	Sjekira (COCI20_sjekira)	C++20	110 / 110	48 ms	7624 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 3;

int n;
int t[N];
vector<int> adj[N];

bool vis[N];
long long answer = 0;

struct DisjointSet {
    vector<int> lab, save;
    DisjointSet (int n) : lab(n + 3, -1), save(n + 3) {}

    void load() {
        for(int i = 1; i <= n; i++) {
            lab[i] = -1;
            save[i] = t[i];
        }
    }

    int root(int u) {
        return lab[u] < 0 ? u : lab[u] = root(lab[u]);
    }

    bool unite(int u, int v) {
        u = root(u); v = root(v);
        if(u == v) return false;
        if(-lab[u] < -lab[v]) swap(u, v);
        answer += save[u] + save[v];
        lab[u] += lab[v];
        lab[v] = u;
        save[u] = max(save[u], save[v]);
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("SJEKIRA.INP", "r")) {
        freopen("SJEKIRA.INP", "r", stdin);
        freopen("SJEKIRA.OUT", "w", stdout);
    }

    cin >> n;

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

    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    static int lab[N];
    for(int i = 1; i <= n; i++) {
        lab[i] = i;
    }

    sort(lab + 1, lab + 1 + n, [&](int x, int y) {
        return t[x] < t[y];
    });

    DisjointSet dsu(n + 3); dsu.load();
    for(int i = 1; i <= n; i++) {
        int u = lab[i];
        for(int v : adj[u]) if(vis[v]) {
            dsu.unite(u, v);
        }

        vis[u] = true;
    }

    cout << answer << endl;

    return 0;
}

Compilation message (stderr)

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

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