Submission #1160201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160201		12345678	Sirni (COCI17_sirni)	C++17	140 / 140	2210 ms	708060 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=5e6+5;

int n, dsu[nx], mx, idx, res, x, sz, dp[2*kx];
vector<int> v;
vector<pair<int, int>> edg[kx];
set<int> s;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x, s.insert(x), mx=max(mx, x);
    sz=s.size();
    for (int i=0; i<sz; i++) dsu[i]=i;
    for (auto x:s) v.push_back(x);
    s.clear();
    idx=sz-1;
    for (int i=0; i<sz; i++) dp[v[i]]=i;
    for (int i=mx-1; i>=0; i--) if (!dp[i]) dp[i]=dp[i+1];
    for (int i=0; i<sz; i++) 
    {
        for (int j=2*v[i]; j<=mx; j+=v[i]) 
        {
            if (v[dp[j]]-j==0) dsu[find(i)]=find(dp[j]);
            else edg[v[dp[j]]-j].push_back({i, dp[j]});
        }
    }
    for (int i=0; i<sz-1; i++) edg[v[i+1]-v[i]].push_back({i, i+1});
    for (int i=0; i<=(mx+1)/2; i++)
    {
        for (auto [u, v]:edg[i])
        {
            //cout<<"edg "<<u<<' '<<v<<' '<<i<<'\n';
            if (find(u)!=find(v)) res+=i, dsu[find(u)]=find(v);
        }
    }
    cout<<res;

}
/*
10
7 10 5 6 4 7 9 8 7 2
*/

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