oj.uz

Submission #1095446

# Submission time Handle Problem Language Result Execution time Memory
1095446 2024-10-02T08:22:39 Z tinnhiemnn Sirni (COCI17_sirni) C++17
140 / 140
 3341 ms 719804 KB 
#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=1e5+2, INF=1e7+2;
int n,pa[N],d;
pii a[N];
long long res;
vector<pii> edge[INF];

int findpa(int u)
{
    return pa[u]==u ? u : pa[u]=findpa(pa[u]);
}
bool uni(int u, int v)
{
    u=findpa(u); v=findpa(v);
    if (u==v) return 0;
    pa[v]=u; return 1;
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n;
    for (int i=1;i<=n;i++) {cin>>a[i].first; a[i].second = i;}
    sort(a+1, a+n+1);

    for (int i=1;i<=n;i++) pa[i]=i;

    for (int i=1;i<=n;i++)
    {
        int j=i+1;
        for (int k=a[i].first; k<=INF && j<=n; k+=a[i].first)
        {
            while (j<=n && a[j].first < k) j++;
            if (j<=n) {edge[a[j].first % a[i].first].pb({a[i].second, a[j].second}); j++;}
        }
    }

    for (int x=0;x<=INF;x++)
        for (pii p : edge[x])
    {
        if (uni(p.first, p.second)) {res+=x; d++;}
        if (d == n-1) {cout<<res; return 0;}
    }



}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 235344 KB Output is correct
2 Correct 109 ms 238420 KB Output is correct
3 Correct 101 ms 235604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 235344 KB Output is correct
2 Correct 106 ms 236368 KB Output is correct
3 Correct 105 ms 235344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 235348 KB Output is correct
2 Correct 107 ms 235088 KB Output is correct
3 Correct 98 ms 235340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1929 ms 246860 KB Output is correct
2 Correct 1738 ms 285972 KB Output is correct
3 Correct 2025 ms 258552 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 237144 KB Output is correct
2 Correct 2423 ms 527464 KB Output is correct
3 Correct 1661 ms 249600 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1908 ms 260920 KB Output is correct
2 Correct 2120 ms 317496 KB Output is correct
3 Correct 1846 ms 251556 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 239644 KB Output is correct
2 Correct 2148 ms 307532 KB Output is correct
3 Correct 1851 ms 255960 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 250012 KB Output is correct
2 Correct 1872 ms 560012 KB Output is correct
3 Correct 1274 ms 252976 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 249496 KB Output is correct
2 Correct 2990 ms 673088 KB Output is correct
3 Correct 1396 ms 260972 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 237908 KB Output is correct
2 Correct 3341 ms 719804 KB Output is correct
3 Correct 1973 ms 260660 KB Output is correct