oj.uz

Submission #1096017

# Submission time Handle Problem Language Result Execution time Memory
1096017 2024-10-03T15:00:11 Z trinhbaongoc3006 Sirni (COCI17_sirni) C++17
140 / 140
 2785 ms 202512 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;
};
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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Correct 159 ms 25092 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 2 ms 1372 KB Output is correct
2 Correct 1122 ms 197620 KB Output is correct
3 Correct 5 ms 2008 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 179 ms 18516 KB Output is correct
2 Correct 489 ms 30804 KB Output is correct
3 Correct 190 ms 17724 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3324 KB Output is correct
2 Correct 183 ms 26068 KB Output is correct
3 Correct 180 ms 17772 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 30720 KB Output is correct
2 Correct 506 ms 30760 KB Output is correct
3 Correct 197 ms 18472 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8532 KB Output is correct
2 Correct 454 ms 29852 KB Output is correct
3 Correct 209 ms 17980 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 18952 KB Output is correct
2 Correct 2025 ms 104924 KB Output is correct
3 Correct 248 ms 31428 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 19004 KB Output is correct
2 Correct 2630 ms 202512 KB Output is correct
3 Correct 584 ms 104732 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4880 KB Output is correct
2 Correct 2785 ms 202096 KB Output is correct
3 Correct 218 ms 18052 KB Output is correct