oj.uz

Submission #345147

# Submission time Handle Problem Language Result Execution time Memory
345147 2021-01-07T05:23:31 Z ThinGarfield Sirni (COCI17_sirni) C++11
0 / 140
 5000 ms 6436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 6288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1327 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 2680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 6420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 6416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2649 ms 1644 KB Output isn't correct
2 Halted 0 ms 0 KB -