oj.uz

Submission #754718

# Submission time Handle Problem Language Result Execution time Memory
754718 2023-06-08T12:42:26 Z PanosPask Sirni (COCI17_sirni) C++14
140 / 140
 2982 ms 575676 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define pb push_back

using namespace std;

typedef pair<int, int> pi;
typedef long long ll;

struct dsu {

    int size;
    vector<int> rep;
    vector<int> rank;

    void init(int n) {
        size = n;
        rank.assign(size, 0);

        rep.resize(size);
        for (int i = 0; i < n; i++)
            rep[i] = i;
    }

    int find(int a) {
        if (a != rep[a])
            rep[a] = find(rep[a]);

        return rep[a];
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b)
            return false;

        if (rank[a] == rank[b])
            rank[a]++;
        else if (rank[b] < rank[a])
            swap(a, b);

        rep[b] = a;
        return true;
    }
};

struct Edge {
    int a, b, w;
};

int n;

const int MAXC = 1e7 + 2;
// const int MAXC = 15 + 2;
const int INF = 1e6;

vector<int> p;
vector<pi> nxt_largest;
vector<vector<pi>> w;
vector<int> first_after;
dsu graph;

int main(void)
{
    scanf("%d", &n);
    w.resize(MAXC + 1);
    graph.init(n);
    first_after.assign(MAXC + 1, INF);

    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        if (first_after[num] == INF) {
            p.push_back(num);
            first_after[num] = p.size() - 1;
        }
    }
    sort(p.begin(), p.end());

    for (int i = 0; i < p.size(); i++)
        first_after[p[i]] = i;
    for (int v = MAXC - 1; v > 0; v--)
        first_after[v] = min(first_after[v], first_after[v + 1]);

    // Generate edges
    for (int i = 0; i < p.size(); i++) {
        int cur = p[i];
        int prvadd = -1;

        int b = first_after[cur + 1];
        if (b == INF)
            break;

        int cost = p[b] % p[i];
        w[cost].pb(mp(i, b));
        prvadd = b;

        for (cur = 2 * p[i]; cur < MAXC; cur += p[i]) {
            int b = first_after[cur];
            if (b == prvadd)
                continue;
            if (b == INF)
                break;

            cost = p[b] % p[i];
            w[cost].pb(mp(i, b));
            prvadd = b;
        }
    }

    // Counting sort
    ll cost = 0;
    for (int i = 0; i < MAXC; i++)
        for (auto& e : w[i])
            if (graph.unite(e.f, e.s))
                cost += i;

    printf("%lld\n", cost);

    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < p.size(); i++)
      |                     ~~^~~~~~~~~~
sirni.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~
sirni.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sirni.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d", &num);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 274400 KB Output is correct
2 Correct 261 ms 276708 KB Output is correct
3 Correct 225 ms 274560 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 274372 KB Output is correct
2 Correct 388 ms 275036 KB Output is correct
3 Correct 212 ms 274420 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 274436 KB Output is correct
2 Correct 212 ms 274232 KB Output is correct
3 Correct 203 ms 274412 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 284960 KB Output is correct
2 Correct 391 ms 312604 KB Output is correct
3 Correct 276 ms 290800 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 276036 KB Output is correct
2 Correct 298 ms 297536 KB Output is correct
3 Correct 256 ms 285644 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 297128 KB Output is correct
2 Correct 444 ms 327440 KB Output is correct
3 Correct 280 ms 289600 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 277928 KB Output is correct
2 Correct 412 ms 322008 KB Output is correct
3 Correct 285 ms 288828 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 287712 KB Output is correct
2 Correct 1745 ms 484308 KB Output is correct
3 Correct 394 ms 290656 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 287844 KB Output is correct
2 Correct 2781 ms 575676 KB Output is correct
3 Correct 409 ms 294584 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 276636 KB Output is correct
2 Correct 2982 ms 570676 KB Output is correct
3 Correct 287 ms 290780 KB Output is correct