/*
weak weak we ak we akwea weak we
weak weak we ak weak weak we ak we
weakweak we ak wea ak we akwe
wea we ak we ak we akwe
wea we ak we ak we akwe
wea eak weak we ak we ak we
wea wea ak we ak weak we
we
we ak wea ak weak we
we ak wea weak wea eak we
we ak we ak wea wea we we
weak we ak we we we we
we we ak we we we we
we wea weak wea wea weak weak
weak wea akw weak weak
*/
//#define _GLIBCXX_DEBUG //is only used when couldn't find bug
using namespace std;
#pragma GCC optimize ("Ofast")
//headers
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
//defines
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair
//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n
//loops
#define REP(n) for (int ___=n > 0 ? n : 0;___--;)
#define REP0(i,n) for (int i=0,___=n;i<___;++i)
#define REP1(i,n) for (int i=1,___=n;i<=___;++i)
#define MEM(e,val) memset (e,val,sizeof(e))
/*
every one is so dian except me
still too weak 咩噗
*/
//IO
#include <cstdio>
#include <iostream>
#include <fstream>
#define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);
//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
//tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
*/
//constants
#include <climits>
const int maxn = 1e7+10,mod = 0;
const long long inf = 0;
const double eps = 0;
//workspace
bool app[maxn];
struct _edge{
int u,v;
int w;
bool operator<(_edge a){
return w < a.w;
}
_edge(int u,int v,int w): u(u), v(v), w(w){}
};
struct DSU{
int dsu[maxn],size[maxn];
void init(vector <int> &v){
for (auto &i:v){
dsu[i] = i;
size[i] = 1;
}
}
int query(int k){
return k == dsu[k] ? k : dsu[k] = query(dsu[k]);
}
void merge(int u,int v){
u = query(u); v = query(v);
if (size[u] < size[v]) swap(u,v);
dsu[v] = u;
size[u] += size[v];
}
}dsu;
inline void solve(){
int n;
cin >> n;
int mx = 1;
REP(n){
int x;
cin >> x;
app[x] = true;
mx = max(mx,x);
}
vector <int> vv;
vv.reserve(n);
REP1(i,mx) if (app[i]) vv.pb(i);
vector <_edge> edge;
for (auto &x:vv){
auto it = upper_bound(iter(vv),x);
if (it != vv.end() and *it - x < x) edge.pb(_edge(x, *it, *it - x));
for (int k=x+x;k<=mx;k+=x){
auto it = lower_bound(iter(vv),k);
if (it == vv.end()) break;
k = *it - *it % x;
edge.pb(_edge(x, *it, *it - k));
}
}
sort(iter(edge));
dsu.init(vv);
LL ans = 0;
int c = vv.size();
for (auto &[u,v,w]:edge){
if (dsu.query(u) != dsu.query(v)){
//cout << u << ' ' << v << '\n';
dsu.merge(u,v);
ans += w;
if (!--c) break;
}
}
cout << ans;
}
/*
5
9 12 13 21 23
*/
signed main(){
want_to_be_more_dian
//int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
//int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
//cout << "Case #" << i << ": ",//use in Google, FB competitions
solve();//always used
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
10828 KB |
Output is correct |
| 2 |
Correct |
29 ms |
8356 KB |
Output is correct |
| 3 |
Correct |
17 ms |
11624 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2500 KB |
Output is correct |
| 3 |
Correct |
20 ms |
11528 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
11640 KB |
Output is correct |
| 2 |
Correct |
16 ms |
6348 KB |
Output is correct |
| 3 |
Correct |
14 ms |
11616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
155 ms |
21524 KB |
Output is correct |
| 2 |
Correct |
576 ms |
55672 KB |
Output is correct |
| 3 |
Correct |
202 ms |
27516 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
10944 KB |
Output is correct |
| 2 |
Correct |
285 ms |
51100 KB |
Output is correct |
| 3 |
Correct |
142 ms |
17904 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
360 ms |
51008 KB |
Output is correct |
| 2 |
Correct |
698 ms |
100880 KB |
Output is correct |
| 3 |
Correct |
190 ms |
26968 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
48 ms |
6896 KB |
Output is correct |
| 2 |
Correct |
677 ms |
100748 KB |
Output is correct |
| 3 |
Correct |
199 ms |
26992 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
251 ms |
102984 KB |
Output is correct |
| 2 |
Correct |
3300 ms |
404512 KB |
Output is correct |
| 3 |
Correct |
329 ms |
106120 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
264 ms |
102872 KB |
Output is correct |
| 2 |
Execution timed out |
5007 ms |
459112 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
74 ms |
80716 KB |
Output is correct |
| 2 |
Execution timed out |
5024 ms |
443356 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
