Submission #647425

#	Time	Username	Problem	Language	Result	Execution time	Memory
647425		billyisme	Sirni (COCI17_sirni)	C++14	98 / 140	2146 ms	786432 KiB

sirni

#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define pb push_back
#define pk pop_back
#define pii pair<int,int>
#define fi first 
#define se second
#define int long long 
const int N =2e5+5 ,  oo = 1e9 ;
const ll sm = 1e9+7,cs=330 ,inf = 1e17; 
struct edge 
{
    int u , v , w;  
    bool operator <(const edge& a  )const 
    {
        return w<a.w; 
    }
};
int n ; 
vector<int>a;
vector<edge>q;
int pa[N];
int max_val;  
void inp()
{
    cin>> n; 
    a.resize(n) ; 
    for(int i= 0;i<n;i++)
    {
        cin>>a[i] ; 
    }
    sort(a.begin(),a.end()); 
    a.resize(unique(a.begin(),a.end())-a.begin());
    n = a.size() ;      
    max_val=a.back() ;
}

void init()
{
    for(int i =0 ;i<n;i++)
    {
        pa[i] =  i ;
    }
}
void build()
{
    for(int i=0;i<n-1;i++)
    {
        for(int j =a[i];j<=max_val;j+=a[i])
        {
            int pos = lower_bound(a.begin()+i+1,a.end(),j) - a.begin() ; 
            if(pos>=n)continue ; 
            if(a[pos]-j>a[i])continue ;
            q.pb({i,pos,a[pos]-j}) ;  
        }
    }
}
ll res=0 ;  
ll goc(int u )
{
    return (pa[u]==u?u:pa[u]=goc(pa[u])) ;
}   
void hop(int u , int v ,int w )
{
    int chau=goc(u) ; 
    int chav=goc(v) ; 
    if(chau==chav)return ;
    res+=w;  
    pa[chau]=chav; 
}
void solve()
{
    sort(q.begin(),q.end()) ; 
    for(int i= 0 ;i<q.size();i++)
    {
        int  u =q[i].u ; 
        int v =q[i].v ;  
        hop(u,v,q[i].w) ;       
    }
    cout<<res ; 
}
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0) ; cout.tie(0);
    int t ; 
    t = 1; 
    while(t--)
    {
        inp(); 
        init(); 
        build(); 
        solve() ; 
    }
    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'void solve()':
sirni.cpp:75:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i= 0 ;i<q.size();i++)
      |                   ~^~~~~~~~~
sirni.cpp: At global scope:
sirni.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 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