제출 #1245852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245852		khoi	Sirni (COCI17_sirni)	C++20	0 / 140	27 ms	5604 KiB

sirni

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

struct Edge {
    int u, v;
    long long w;
    bool operator<(Edge const& o) const { return w < o.w; }
};

struct DSU {
    vector<int> par, rank;
    DSU(int n): par(n+1), rank(n+1, 0) {}
    void make_set(int u) {
        par[u] = u;
        rank[u] = 0;
    }
    int find_set(int v) {
        return par[v] == v ? v : par[v] = find_set(par[v]);
    }
    bool union_set(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return false;
        if (rank[u] < rank[v]) swap(u, v);
        par[v] = u;
        if (rank[u] == rank[v]) rank[u]++;
        return true;
    }
};

int n, p[100005];
vector<Edge> e;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];

    // Tìm chỉ số có giá trị nhỏ nhất
    int idx = 1;
    for (int i = 2; i <= n; i++) {
        if (p[i] < p[idx]) idx = i;
    }

    // Thêm các cạnh từ các đỉnh khác đến đỉnh nhỏ nhất
    for (int i = 1; i <= n; i++) {
        if (i == idx) continue;
        int w = min(p[i] % p[idx], p[idx] % p[i]);
        e.push_back({idx, i, w});
    }

    // Thêm cạnh giữa các phần tử gần nhau (kề nhau khi sort)
    vector<pair<int, int>> v(n);
    for (int i = 1; i <= n; i++) {
        v[i-1] = {p[i], i};  // value, index
    }
    sort(v.begin(), v.end());
    for (int i = 1; i < n; i++) {
        int a = v[i-1].second;
        int b = v[i].second;
        int w = min(p[a] % p[b], p[b] % p[a]);
        e.push_back({a, b, w});
    }

    sort(e.begin(), e.end());

    DSU d(n);
    for (int i = 1; i <= n; i++) d.make_set(i);

    long long total = 0;
    int count = 0;
    for (auto [u, v, w] : e) {
        if (d.union_set(u, v)) {
            total += w;
            if (++count == n - 1) break;
        }
    }

    cout << total << '\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14