Submission #1168609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168609		Hanksburger	Sirni (COCI17_sirni)	C++20	112 / 140	5093 ms	82984 KiB

sirni

#include <bits/stdc++.h>
#define int long long
using namespace std;
int exist[10000005], par[100005], sz[100005];
vector<int> adj[100005], vec;
int findPar(int u)
{
    return par[u]==u?u:(par[u]=findPar(par[u]));
}
int addEdge(int u, int v)
{
    if (findPar(u)==findPar(v))
        return 0;
    if (sz[par[u]]>sz[par[v]])
        swap(u, v);
    sz[par[v]]+=sz[par[u]];
    par[par[u]]=par[v];
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans=0;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        int x;
        cin >> x;
        vec.push_back(x);
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end())-vec.begin());
    for (int i=0; i<vec.size(); i++)
    {
        exist[vec[i]]=i+1;
        par[i]=i;
        sz[i]=1;
    }
    for (int i=0;; i++)
    {
        for (int j=i+1; j<=10000000; j++)
        {
            if (!exist[j])
                continue;
            if (j<=100)
            {
                for (int k=0; k<vec.size(); k++)
                    if (vec[k]%j==i && addEdge(exist[j]-1, k))
                        ans+=i;
            }
            else
            {
                for (int k=j+i; k<=10000000; k+=j)
                    if (exist[k] && addEdge(exist[j]-1, exist[k]-1))
                        ans+=i;
            }
        }
        if (sz[findPar(0)]==vec.size())
        {
            cout << ans;
            return 0;
        }
    }
}

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