| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 489905 |
2021-11-25T03:17:55 Z |
yungyao |
Sirni (COCI17_sirni) |
C++17 |
|
385 ms |
296392 KB |
/*
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];
vector <pii> edge[maxn];
struct DSU{
int dsu[maxn];
void init(vector <int> &v){
for (auto &i:v) dsu[i] = i;
}
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);
dsu[v] = u;
}
}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);
for (auto &x:vv){
auto it = upper_bound(iter(vv),x);
if (it != vv.end() and *it - x < x) edge[*it - x].pb(mkp(x, *it));
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[*it - k].pb(mkp(x, *it));
}
}
dsu.init(vv);
LL ans = 0;
int c = vv.size();
REP1(w,mx) for (auto &[u,v]:edge[w]){
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
242056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
235256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
242472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
252 ms |
249660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
241620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
385 ms |
261212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
239468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
296392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
372 ms |
296220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
281288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
