Submission #1273953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273953		quan606303	Sirni (COCI17_sirni)	C++20	14 / 140	1135 ms	851968 KiB

sirni

/*
 * @Author: RMQuan 
 * @Date: 2025-09-29 00:33:39 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-09-29 01:14:55
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
const int maxx=1e7+7;
int n,a[maxn];
int pos[maxx];
struct DSU 
{
    int N,scc;
    vector<int> par,sz;
    DSU(int n)
    {
        N=n;
        scc=n;
        par.assign(n+5,0);
        sz.assign(n+5,0);
        for (int i=1;i<=n;i++)
        {
            par[i]=i;
            sz[i]=1;
        }
    }
    int find_set(int x)
    {
        if (x==par[x])return x;
        return par[x]=find_set(par[x]);
    }
    bool union_set(int x,int y)
    {
        scc--;
        x=find_set(x);
        y=find_set(y);
        if (x==y)return false;
        if (sz[x]<sz[y])swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
        return true;
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    DSU dsu(n);
    int ans=0;
    for (int i=1;i<maxx;i++)pos[i]=-1;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        if (pos[a[i]]==-1)pos[a[i]]=i;
        else dsu.union_set(pos[a[i]],i);
    }
    for (int i=1;i<maxx;i++)
    {
        if (pos[i]!=-1)
        {
            for (int j=2*i;j<maxx;j+=i)if (pos[j]!=-1)dsu.union_set(pos[i],pos[j]);
        }
    }
    vector<int> val;
    for (int i=1;i<=n;i++)val.push_back(a[i]);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    vector<pair<int,pair<int,int> > > edge;
    for (int i=1;i<maxx;i++)
    {
        if (pos[i]!=-1)
        {
            for (int j=i;j<maxx;j+=i)
            {
                auto it=upper_bound(val.begin(),val.end(),j);
                if (it!=val.end())
                {
                    edge.push_back({min((*it%i),(i%(*it))),{pos[i],pos[*it]}});
                }
            }
        }
    }
    sort(edge.begin(),edge.end());
    for (auto i:edge)if (dsu.union_set(i.se.fi,i.se.se))ans+=i.fi;
    cout<<ans;
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

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