Submission #1108098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108098		overwatch9	Kronican (COCI16_kronican)	C++17	10 / 100	1 ms	508 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector <int> link, sz;
    DSU (int s) {
        link = sz = vector <int> (s+1);
        for (int i = 0; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
        }
    }
    int head(int x) {
        if (link[x] == x)
            return x;
        return link[x] = head(link[x]);
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (same(a, b))
            return;
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += sz[b];
        link[b] = a;
    }
};
int main() {
    int n, k;
    cin >> n >> k;
    vector <vector <int>> adj(n, vector <int> (n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> adj[i][j];
    }
    vector <array <int, 3>> edges;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            edges.push_back({adj[i][j], i, j});
        }
    }
    sort(edges.begin(), edges.end());
    int ans = 0;
    DSU dsu(n+1);
    for (int i = 0; i < (int)edges.size() && k < n; i++) {
        int c = edges[i][0], a = edges[i][1], b = edges[i][2];
        if (dsu.same(a, b))
            continue;
        ans += c;
        dsu.unite(a, b);
        k++;
    }
    cout << ans << '\n';
}

• Subtask 1: 10 / 100