oj.uz

답안 #481746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481746 2021-10-21T14:41:10 Z Johann Sirni (COCI17_sirni) C++14
0 / 140
 200 ms 25512 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) {
            if (skip[k]) continue;
            auto it2 = lower_bound(it, cards.end(), k);
            idx2 = it2 - cards.begin();
            if (*it2 % c == 0) {
                skip[idx2] = true;
                uf.unite(idx, idx2);
                it2++;
            }
            if (it2 != cards.end() && *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";
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 113 ms 15500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 2116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 200 ms 25512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 5324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 11900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 12036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 2760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -