Submission #1106912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106912		vjudge1	Sirni (COCI17_sirni)	C++17	0 / 140	416 ms	106044 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod=1e9+7;
#define fi first
#define se second
int n,u,minn[10000005],pa[10000005];
vector<int> vec;
vector<pair<int,pair<int,int>>> krk;
ll ketqua;
int find_pa(int u)
{
    if (pa[u]==u) return u;
    return pa[u]=find_pa(pa[u]);
}
void Merge(int u,int v,int x)
{
    u=find_pa(u);
    v=find_pa(v);
    if (u==v) return;
    ketqua+=x;
    pa[u]=v;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        cin>>u;
        pa[u]=u;
        vec.push_back(u);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(begin(vec),end(vec)),end(vec));
    for (int i=0;i<=10000001;++i) minn[i]=-1;
    for (int i=vec.size()-1;i>=1;--i)
    {
        for (int j=vec[i];j>vec[i-1];--j) minn[j]=vec[i];
    }
    for (int i=0;i<=vec[0];++i) minn[i]=vec[0];
    for (int i=0;i<vec.size();++i)
    {
        if (vec[i]==0) continue;
        int hao=vec[i];
        for (int j=hao;j<=10000000;j+=hao)
        {
            if (minn[j]==-1 || minn[j]>j+hao) continue;
            krk.push_back({min(hao%minn[j],minn[j]%hao),{hao,minn[j]}});
        }
    }
    sort(krk.begin(),krk.end());
    for (int i=0;i<krk.size();++i)
    {
        Merge(krk[i].se.fi,krk[i].se.se,krk[i].fi);
        //cout<<krk[i].se.fi<<" "<<krk[i].se.se<<" "<<krk[i].fi<<'\n';
    }
    cout<<ketqua;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0;i<vec.size();++i)
      |                  ~^~~~~~~~~~~
sirni.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i=0;i<krk.size();++i)
      |                  ~^~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14