Submission #1288639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288639		nemkho	Sirni (COCI17_sirni)	C++17	14 / 140	1418 ms	851968 KiB

sirni

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, _max, a[N], siz[N], par[N];
ll res;
struct haha
{
    int u, v, w;
};
vector <haha> edge;
void inp()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        _max = max(_max, a[i]);
    }
}
void make_set ()
{
    for (int i = 1; i <= n; i++)
    {
        siz[i] = 1;
        par[i] = i;
    }
}
int find_set (int x)
{
    return (par[x] == x ? x : par[x] = find_set(par[x]));
}
bool union_set (int u, int v)
{
    u = find_set(u);
    v = find_set(v);
    if (u == v)
        return false;
    if (siz[u] < siz[v])
        swap(u, v);
    par[v] = u;
    siz[u] += siz[u];
    return true;
}
bool cmp (const haha &a, const haha &b)
{
    return a.w < b.w;
}
void solve()
{
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        if (i < n)
            edge.push_back({i, i + 1, a[i+1] % a[i]});
        for (int j = 2*a[i]; j <= _max; j += a[i])
        {
            int tmp = lower_bound(a + 1, a + n + 1, j) - a;
         //   cout << i << " " << a[tmp] % a[i] << " " << j << "\n";
            edge.push_back({i, tmp, a[tmp] % a[i]});
        }
    }
    sort(edge.begin(), edge.end(), cmp);
    make_set();
    for (int i = 0; i < edge.size(); i++)
    {
        int u = edge[i].u, v = edge[i].v;
        if (union_set(u, v))
        {
            res += edge[i].w;
        }
    }
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

• 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