oj.uz

Submission #866713

# Submission time Handle Problem Language Result Execution time Memory
866713 2023-10-26T19:37:57 Z smirichto Sirni (COCI17_sirni) C++17
84 / 140
 2040 ms 786432 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

struct DSU{
    vector<int> dsu ;
    void init(int n){dsu.resize(n+1) ; for(int i = 0 ; i<=n ; i++) dsu[i] = -1 ;}
    int size_(int a){return -dsu[find_(a)] ;}
    int find_(int a){return (dsu[a]<0 ? a:dsu[a]=find_(dsu[a])) ;}
    void add_(int a , int b){
        int x = find_(a) ;int y = find_(b) ;if(x==y) return ;
        if(dsu[x]>dsu[y]) swap(x,y) ;
        dsu[x] += dsu[y] ;
        dsu[y] = x ;
    }
};


void solve() {
    int n ; cin>>n ;
    vector<pair<int,int>> v ;
    map<int,int> mp ;
    int nax = 0 ;
    for(int i = 1 ; i<=n ; i++){
        int x ; cin>>x ;
        ckmax(nax , x) ;
        if(mp.count(x)) continue;
        mp[x] = 1 ;
        v.pb({x , i}) ;
    }
    ++nax ;
    vector<array<int,3>> edges ;
    sort(all(v)) ;
    for(int i = 0 ; i<v.size() ; i++){
        if(i+1<v.size()){
            edges.pb({v[i+1].F % v[i].F , v[i].S , v[i+1].S}) ;
        }
        for(int j = v[i].F + v[i].F ; j<nax ; j+=v[i].F){
            auto it = lower_bound(all(v) , make_pair(j , -1)) ;
            if(it!=v.end()){
                edges.pb({it->F % v[i].F , v[i].S , it->S}) ;
            }
        }
    }
    DSU dsu ; dsu.init(n+5) ;
    sort(all(edges)) ;
    clean(edges) ;
    ll ans = 0 ;
    for(auto a : edges){
        int x = a[0] , u = a[1] , vv = a[2] ;
        if(dsu.find_(u) == dsu.find_(vv)) continue;
        ans+= x ;
        dsu.add_(u , vv) ;
    }
    cout<<ans<<endl;
}

int main() {

    io();
    ll tt = 1;
    //cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message

sirni.cpp: In function 'void solve()':
sirni.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0 ; i<v.size() ; i++){
      |                     ~^~~~~~~~~
sirni.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(i+1<v.size()){
      |            ~~~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 339 ms 51536 KB Output is correct
3 Correct 4 ms 856 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Runtime error 609 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 31204 KB Output is correct
2 Correct 1083 ms 57244 KB Output is correct
3 Correct 489 ms 55080 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4304 KB Output is correct
2 Correct 451 ms 51400 KB Output is correct
3 Correct 300 ms 30968 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 56012 KB Output is correct
2 Correct 1442 ms 105612 KB Output is correct
3 Correct 443 ms 31140 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 9276 KB Output is correct
2 Correct 1402 ms 104220 KB Output is correct
3 Correct 446 ms 31412 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 32436 KB Output is correct
2 Runtime error 1513 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 32888 KB Output is correct
2 Runtime error 1354 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5440 KB Output is correct
2 Runtime error 2040 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -