oj.uz

Submission #982955

# Submission time Handle Problem Language Result Execution time Memory
982955 2024-05-15T06:05:38 Z ndan Sirni (COCI17_sirni) C++14
126 / 140
 5000 ms 400736 KB 
// Practice makes perfect
#include <bits/stdc++.h>
#include <set>
using namespace std;

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define file ""
#define ll long long
const int maxn = 1e5 + 5;

int n, p[maxn], lab[maxn];
set<int> s;
ll ans = 0;

struct Edge {
    int u, v, w;
};

vector<Edge> edges;

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

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

bool unite(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b)
        return 0;
    if (lab[a] > lab[b])
        swap(a, b);
    lab[a] += lab[b];
    lab[b] = a;
    return 1;
}

int main() {
    fastIO
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        s.insert(x);
    }
    vector<int> v = vector<int>(s.begin(), s.end());
    if (v[0] == 1 || v.size() == 1) {
        cout << 0;
        return 0;
    }
    memset(lab, -1, sizeof lab);
    n = v.size();
    int mx = v[n - 1];
    for (int i = 0; i < n; ++i) {
        int j = i;
        for (int val = v[i]; val <= mx; val += v[i]) {
            int last = j;
            while (j + 1 < n && v[j] < val)
                j++;
            if (v[j] == v[i])
                j++;
            if (j != n && last != j) {
                Edge e;
                e.u = i;
                e.v = j;
                e.w = v[j] % v[i];
                edges.push_back(e);
            }
        }
    }
    sort(edges.begin(), edges.end(), cmp);
    for (int i = 0; i < edges.size(); ++i)
        if (unite(edges[i].u, edges[i].v))
            ans += edges[i].w;
    cout << ans;
    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < edges.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 26 ms 3924 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 122 ms 1736 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 984 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2078 ms 18628 KB Output is correct
2 Correct 2040 ms 55208 KB Output is correct
3 Correct 1405 ms 30128 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4804 KB Output is correct
2 Correct 270 ms 51064 KB Output is correct
3 Correct 1484 ms 17760 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2258 ms 55564 KB Output is correct
2 Correct 2283 ms 104780 KB Output is correct
3 Correct 1997 ms 31360 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 11076 KB Output is correct
2 Correct 2104 ms 103764 KB Output is correct
3 Correct 1595 ms 30380 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2179 ms 31592 KB Output is correct
2 Correct 4393 ms 400736 KB Output is correct
3 Correct 2240 ms 31232 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2181 ms 31432 KB Output is correct
2 Execution timed out 5027 ms 399788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 5068 KB Output is correct
2 Correct 4915 ms 399036 KB Output is correct
3 Correct 1649 ms 30460 KB Output is correct