oj.uz

답안 #489905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489905 2021-11-25T03:17:55 Z yungyao Sirni (COCI17_sirni) C++17
0 / 140
 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;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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