#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
struct DSU{
vi size, par;
DSU(int n) : size(n, 1), par(n, -1) {}
int find_set(int a){
return (par[a] == -1 ? a : par[a] = find_set(par[a]));
}
bool unite(int a, int b){
a = find_set(a), b = find_set(b);
if(a == b) return false;
if(size[a] < size[b])
swap(a, b);
par[b] = a;
size[a] += size[b];
return true;
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vi cards(n);
for(int &i : cards)
cin >> i;
sort(cards.begin(), cards.end());
cards.erase(unique(cards.begin(), cards.end()), cards.end());
int largest = cards.back(), cost = 0;
vi next_largest(largest + 1, -1);
for(int i = 0; i < n; i++)
next_largest[cards[i]] = i;
for(int i = largest - 1; i >= 0; i--)
if(next_largest[i] == -1)
next_largest[i] = next_largest[i + 1];
vector<vector<pii>> pos_edges(largest + 1);
for(int i = 0; i < n - 1; i++){
pos_edges[cards[i + 1] % cards[i]].emplace_back(i, i + 1);
for(int at = 2 * cards[i]; at <= largest; at += cards[i]){
int good_mod = next_largest[at];
pos_edges[cards[good_mod] % cards[i]].emplace_back(i, good_mod);
}
}
DSU dsu(n);
for(int i = 0; i <= largest; i++){
for(auto edge : pos_edges[i]){
if(dsu.unite(edge.fi, edge.se))
cost += i;
}
}
cout << cost;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
313428 KB |
Output is correct |
2 |
Incorrect |
209 ms |
368896 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
313428 KB |
Output is correct |
2 |
Correct |
136 ms |
312952 KB |
Output is correct |
3 |
Correct |
146 ms |
313516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
56 ms |
53756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
21 ms |
35676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
85 ms |
76596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
14492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
212 ms |
340564 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
198 ms |
350252 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
152 ms |
318484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |