oj.uz

Submission #481750

# Submission time Handle Problem Language Result Execution time Memory
481750 2021-10-21T14:50:49 Z Johann Sirni (COCI17_sirni) C++14
84 / 140
 913 ms 60084 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 41 ms 3536 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 332 KB Output is correct
2 Correct 207 ms 352 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
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2244 KB Output is correct
2 Correct 106 ms 14036 KB Output is correct
3 Incorrect 102 ms 15752 KB Output isn't correct

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 21200 KB Output is correct
2 Correct 641 ms 10336 KB Output is correct
3 Correct 185 ms 26908 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 10876 KB Output is correct
2 Correct 746 ms 14292 KB Output is correct
3 Correct 276 ms 9020 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5008 KB Output is correct
2 Correct 913 ms 60084 KB Output is correct
3 Correct 136 ms 9712 KB Output is correct