Submission #866712

#	Time	Username	Problem	Language	Result	Execution time	Memory
866712		smirichto	Sirni (COCI17_sirni)	C++17	84 / 140	2084 ms	786432 KiB

sirni

#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 (stderr)

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 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14