Submission #345147

#	Time	Username	Problem	Language	Result	Execution time	Memory
345147		ThinGarfield	Sirni (COCI17_sirni)	C++11	0 / 140	5092 ms	6436 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second

constexpr ll big = 1e18 + 18;
constexpr int maxn = 10e5 + 5;
int n;
int p[maxn];
ll dist[maxn];
unordered_set<int> notdone;

ll weight(int a, int b) { return min(p[a] % p[b], p[b] % p[a]); }

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        dist[i] = weight(0, i);
        notdone.emplace(i);
    }
    notdone.erase(0);
    ll COST = 0;
    dist[0] = 0;

    while (!notdone.empty()) {
        ll mindist = big;
        int minode = -1;
        for (int node : notdone) {
            if (dist[node] < mindist) {
                mindist = node;
                minode = node;
            }
        }
        notdone.erase(minode);
        COST += dist[minode];
        dist[minode] = 0;
        for (int nbr : notdone) {
            dist[nbr] = min(dist[nbr], weight(minode, nbr));
        }
    }
    cout << COST << '\n';
    return 0;
}

• 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