oj.uz

Submission #1096018

# Submission time Handle Problem Language Result Execution time Memory
1096018 2024-10-03T15:02:06 Z trinhbaongoc3006 Sirni (COCI17_sirni) C++17
140 / 140
 2534 ms 202356 KB 
#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;
    bool operator < (const edge &rhs) const
    {
        return w < rhs.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;
}
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());
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Correct 125 ms 25216 KB Output is correct
3 Correct 3 ms 1564 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 827 ms 197620 KB Output is correct
3 Correct 4 ms 2004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 18532 KB Output is correct
2 Correct 435 ms 30764 KB Output is correct
3 Correct 169 ms 17464 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3328 KB Output is correct
2 Correct 154 ms 26068 KB Output is correct
3 Correct 154 ms 17576 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 30740 KB Output is correct
2 Correct 481 ms 30588 KB Output is correct
3 Correct 180 ms 18240 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8768 KB Output is correct
2 Correct 407 ms 29824 KB Output is correct
3 Correct 169 ms 17724 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 18992 KB Output is correct
2 Correct 1739 ms 104744 KB Output is correct
3 Correct 229 ms 31220 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19004 KB Output is correct
2 Correct 2503 ms 202356 KB Output is correct
3 Correct 465 ms 104912 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4876 KB Output is correct
2 Correct 2534 ms 201844 KB Output is correct
3 Correct 177 ms 18032 KB Output is correct