제출 #1288643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288643		nemkho	Sirni (COCI17_sirni)	C++17	14 / 140	2886 ms	788348 KiB

sirni

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
vector <int> a;
int n, _max, 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++)
    {
        int x;
        cin >> x;
        a.push_back(x);
        _max = max(_max, x);
    }
}
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.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    for (int i = 0; i < a.size() - 1; i++)
    {
        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.begin(), a.end(), j) - a.begin();
         //   cout << i << " " << a[tmp] % a[i] << " " << j << "\n";
            if (tmp < a.size())
                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