제출 #1160194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160194		12345678	Sirni (COCI17_sirni)	C++17	0 / 140	296 ms	474780 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

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

int n, dsu[nx], mx, idx, res, x, sz;
vector<int> qrs[kx], 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);
    s.clear();
    sz=s.size();
    for (int i=0; i<sz; i++) dsu[i]=i;
    for (auto x:s) v.push_back(x);
    idx=sz-1;
    for (int i=0; i<sz; i++) for (int j=2*v[i]; j<=mx; j+=v[i]) qrs[j].push_back(i);
    for (int i=mx; i>=1; i--)
    {
        while (idx>0&&v[idx-1]>=i) idx--;
        for (auto x:qrs[i]) 
        {
            if (v[idx]==i) dsu[find(idx)]=find(x);
            else edg[v[idx]-i].push_back({idx, x});
        }
        qrs[i].clear();
    }

    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; 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: 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