Submission #1096017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096017		trinhbaongoc3006	Sirni (COCI17_sirni)	C++17	140 / 140	2785 ms	202512 KiB

sirni

#include <bits/stdc++.h>
#define INF int64_t(1e9)
#define pii pair <int, int>
#define pll pair <long long, long long>
#define mp make_pair
#define file "test"
using namespace std;
const int nmax = 2e5 + 5;
const int amax = 1e7;
const long long mod = 1e9 + 7;

int n;
int par[nmax];
struct edge
{
    int u, v, w;
};
vector <edge> adj;
int get(int u)
{
    return par[u] == u ? u : (par[u] = get(par[u]));
}
bool joint(int u, int v)
{
    u = get(u); v = get(v);
    if (u == v) return false;
    par[v] = u;
    return true;
}
bool cmp(edge a, edge b)
{
    return a.w < b.w;
}
set <int> s;
vector <int> a;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    //freopen(file".inp","r",stdin);
    //freopen(file".out","w",stdout);
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>> x;
        s.insert(x);
    }
    for (int i:s) a.push_back(i);
    n = a.size();
    int base = INF;
    for (int i:a) base = min(base, i);
    for (int i=0;i<n;i++)
    {
        int idx = lower_bound(a.begin(), a.end(), a[i] + 1) - a.begin();
        if (idx == n) continue;
        if (a[idx]%a[i] < base) adj.push_back({idx,i,a[idx]%a[i]});
        for (int j=a[i];j<=amax;j+=a[i])
        {
            idx = lower_bound(a.begin(), a.end(), j) - a.begin();
            if (idx == n) break;
            if (a[idx]%a[i] < base) adj.push_back({idx,i,a[idx]%a[i]});
        }
    }
    sort(adj.begin(), adj.end(), cmp);
    for (int i=0;i<nmax;i++) par[i] = i;
    long long res = 0;
    for (edge x:adj)
    {
        //cout << get(x.u) << " " << get(x.v) << "\n";
        //int j = joint(x.u,x.v);
        if (joint(x.u,x.v)) res += x.w;
        //cout << x.u << " " << x.v << " " << x.w << "\n";
    }
    //joint(0,1);

    //for (int i=0;i<=10;i++) cout << get(i) << " ";
    cout << res;
return 0;
}

• 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