Submission #481751

#	Time	Username	Problem	Language	Result	Execution time	Memory
481751		Johann	Sirni (COCI17_sirni)	C++14	140 / 140	904 ms	59772 KiB

sirni

// 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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14