Submission #1154452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154452		windowwife	Sirni (COCI17_sirni)	C++20	140 / 140	1438 ms	746256 KiB

sirni

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 1, maxa = 1e7 + 2;
int n, a, first[maxa];
ll res = 0;
vector<int> v;
vector<pair<int, int>> w[maxa];
struct DSU
{
    vector<int> par;
    void init (int n)
    {
        par.resize(n + 1, -1);
    }
    int find_set (int u)
    {
        if (par[u] < 0) return u;
        return (par[u] = find_set(par[u]));
    }
    bool union_set (int u, int v)
    {
        int pu = find_set(u), pv = find_set(v);
        if (pu == pv) return false;
        if (par[pu] > par[pv]) swap(pu, pv);
        par[pu] += par[pv];
        par[pv] = pu;
        return true;
    }
}dsu;
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        v.push_back(a);
    }
    v.push_back(0);
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    n = v.size() - 1;
    dsu.init(n);
    for (int i = 1; i <= n; i++)
    {
        first[v[i]] = i;
    }
    for (int i = v[n]; i > 0; i--)
    {
        if (first[i] == 0)
        {
            first[i] = first[i + 1];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int x = v[i], k1 = first[x + 1];
        if (k1 != 0)
        {
            int c = min(v[k1] % v[i], v[i] % v[k1]);
            w[c].push_back({i, k1});
        }
        for (int j = 2*x; j <= v[n]; j += x)
        {
            int k = first[j];
            if (k != 0)
            {
                int c = min(v[k] % v[i], v[i] % v[k]);
                w[c].push_back({i, k});
            }
        }
    }
    for (int i = 0; i <= v[n]; i++)
    {
        for (pair<int, int> p : w[i])
        {
            if (dsu.union_set(p.first, p.second))
            {
                res += i;
            }
        }
    }
    cout << res;
}

• 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