oj.uz

답안 #830174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830174 2023-08-18T22:30:46 Z Mathandski Sirni (COCI17_sirni) C++14
98 / 140
 5000 ms 439296 KB 
#include <bits/stdc++.h> 
using namespace std;
#define pb push_back 
#define is insert
#define ll long long
#define V vector
#define MS multiset
#define PL pair<int, int>
#define F first
#define S second
#define PQ priority_queue
#define f0r(i, begin, end) for (int i = begin; i < end; i ++) 
#define For(i, end, begin) for (int i = end; i > begin; i --) 
#define aint(x) x.begin(), x.end()
#define INF 1000000000000000000
#define inf 1000000000
#define MOD 1000000009
#define len(x) (int)x.size()
#define fileread(file) ifstream fin; fin.open((string)file + ".in"); ofstream fout; fout.open((string)file + ".out")
#define fastio ios_base::sync_with_stdio(0); cin.tie(nuintptr)
template<typename T> istream& operator>>(istream& in, V<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, V<T>& a) {for(auto &x : a) out << x << ' '; return out;};

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(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 false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};

int N;
ll ans = 0;
set<int> nums;
int decomp[10000001];
vector<tuple<int, int, int>> edges;

void krustal () {
    int tot = N - 1;
    DSU dsu(N);
    sort(aint(edges));
    for (auto e : edges) {
        if (dsu.unite(get<1>(e), get<2>(e))) {
            ans += get<0>(e);
            if ((--tot) == 0) break;
        }
    }
}

int main () {
    cin >> N;
    DSU dsu(N);
    f0r (i, 0, N) {
        int a; cin >> a;
        nums.is(a);
    }
    int i = 0;
    for (auto n : nums) {
        decomp[n] = (i ++);
    }

    for (auto n : nums) {
        auto pos = nums.lower_bound(n + 1);
        int factor = 1;
        while (pos != nums.end()) {
            if ((*pos) / n > factor) {
                factor = (*pos) / n;
            }
            edges.pb({(*pos) % n, decomp[n], decomp[*pos]});
            pos = nums.lower_bound((++factor) * n);
        }
    }
    
    krustal();
    cout << ans << endl;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4052 KB Output is correct
2 Correct 24 ms 5452 KB Output is correct
3 Correct 4 ms 4500 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 576 KB Output is correct
2 Correct 8 ms 1716 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 319 ms 21512 KB Output is correct
2 Correct 1088 ms 57960 KB Output is correct
3 Correct 399 ms 32972 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 8124 KB Output is correct
2 Correct 380 ms 53480 KB Output is correct
3 Correct 299 ms 18808 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 58340 KB Output is correct
2 Correct 1385 ms 107484 KB Output is correct
3 Correct 383 ms 33692 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 9068 KB Output is correct
2 Correct 1155 ms 106580 KB Output is correct
3 Correct 379 ms 33200 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 424 ms 69248 KB Output is correct
2 Execution timed out 5060 ms 439296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 69212 KB Output is correct
2 Execution timed out 5094 ms 437448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 38528 KB Output is correct
2 Execution timed out 5032 ms 429760 KB Time limit exceeded
3 Halted 0 ms 0 KB -