oj.uz

Submission #866710

# Submission time Handle Problem Language Result Execution time Memory
866710 2023-10-26T19:29:40 Z smirichto Sirni (COCI17_sirni) C++17
84 / 140
 2101 ms 786432 KB 
#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)) ;
    ll ans = 0 ;
    for(auto a : edges){
        int x = a[0] , u = a[1] , v = a[2] ;
        if(dsu.find_(u) == dsu.find_(v)) continue;
        ans+= x ;
        dsu.add_(u , v) ;
    }
    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:65: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]
   65 |     for(int i = 0 ; i<v.size() ; i++){
      |                     ~^~~~~~~~~
sirni.cpp:66: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]
   66 |         if(i+1<v.size()){
      |            ~~~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 303 ms 51336 KB Output is correct
3 Correct 3 ms 1052 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 829 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 2 ms 600 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 285 ms 32680 KB Output is correct
2 Correct 1031 ms 56168 KB Output is correct
3 Correct 497 ms 57248 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5324 KB Output is correct
2 Correct 428 ms 51616 KB Output is correct
3 Correct 290 ms 30628 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 57256 KB Output is correct
2 Correct 1401 ms 105924 KB Output is correct
3 Correct 458 ms 32008 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 10920 KB Output is correct
2 Correct 1368 ms 105464 KB Output is correct
3 Correct 460 ms 31916 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 32448 KB Output is correct
2 Runtime error 1736 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 410 ms 33456 KB Output is correct
2 Runtime error 1552 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 44 ms 4940 KB Output is correct
2 Runtime error 2101 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -