oj.uz

Submission #481751

# Submission time Handle Problem Language Result Execution time Memory
481751 2021-10-21T14:53:11 Z Johann Sirni (COCI17_sirni) C++14
140 / 140
 904 ms 59772 KB 
// https://oj.uz/problem/view/COCI17_sirni
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vb vector<bool>
#define tiii tuple<int, int, int>
#define vtiii vector<tiii>
#define vvtiii vector<vtiii>

struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, c;
    cin >> n;
    set<int> card_set;
    for (int i = 0; i < n; i++) {
        cin >> c;
        card_set.insert(c);
    }
    vi cards(card_set.begin(), card_set.end());
    int mincard = cards.front(), maxcard = cards.back();
    vi numbers_countingsort(mincard + 2); // Komisch wegen Partial Sum später
    DSU uf;
    uf.init(cards.size());
    vtiii edges;
    vb skip(cards.size(), false);
    int d, idx = -1, idx2;
    for (auto it = cards.begin(); it != cards.end(); it++) {
        idx++;
        if (skip[idx]) continue;
        c = *it;
        for (int k = c; k <= maxcard; k += c) {
            auto it2 = lower_bound(it, cards.end(), k);
            idx2 = it2 - cards.begin();
            if (*it2 % c == 0) {
                skip[idx2] = true;
                uf.unite(idx, idx2);
                it2++;
                idx2++;
            }
            if (idx2 < cards.size() && *it2 < k + c) {
                d = *it2 % c;
                if (d >= mincard) continue;
                edges.push_back(make_tuple(d, idx, idx2));
                numbers_countingsort[d+1]++; // komische Logik wegen partial Sum später
            }
        }
    }

    partial_sum(numbers_countingsort.begin(), numbers_countingsort.end()-1, numbers_countingsort.begin());
    vtiii edges2(edges.size());

    for (tiii e : edges) {
        edges2[numbers_countingsort[get<0>(e)]++] = e;
    }

    ll total = 0;
    int k, a, b;
    for (tiii edge : edges2) {
        tie(k, a, b) = edge;
        if (uf.unite(a, b)) total += (ll) k;
    }
    cout << total << "\n";
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if (idx2 < cards.size() && *it2 < k + c) {
      |                 ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 40 ms 3544 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 208 ms 344 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 16084 KB Output is correct
2 Correct 170 ms 19896 KB Output is correct
3 Correct 150 ms 9172 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2240 KB Output is correct
2 Correct 99 ms 13912 KB Output is correct
3 Correct 100 ms 15224 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 25212 KB Output is correct
2 Correct 147 ms 10256 KB Output is correct
3 Correct 108 ms 9020 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5552 KB Output is correct
2 Correct 137 ms 9664 KB Output is correct
3 Correct 138 ms 9472 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 21224 KB Output is correct
2 Correct 619 ms 9440 KB Output is correct
3 Correct 190 ms 26112 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 10728 KB Output is correct
2 Correct 753 ms 13668 KB Output is correct
3 Correct 273 ms 8192 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5000 KB Output is correct
2 Correct 904 ms 59772 KB Output is correct
3 Correct 138 ms 9076 KB Output is correct