oj.uz

Submission #990853

# Submission time Handle Problem Language Result Execution time Memory
990853 2024-05-31T13:53:54 Z doducanh Sirni (COCI17_sirni) C++14
140 / 140
 380 ms 176548 KB 
#include <bits/stdc++.h>

using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=1e5+7;
int n;
int r[maxn];
int sz[maxn];
vector<int>dd;
vector<int>p;
vector<vector<ii>>ed;
int Find(int u)
{
    return (u==r[u])?u:r[u]=Find(r[u]);
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    p.resize(n);
    for(int &c:p){
        cin>>c;
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    int maxx=p.back();
    n=p.size();
    dd.resize(maxx+7);
    for(int i=0;i<maxx;i++)dd[i]=-1;
    for(int i=0;i<n;i++){
        dd[p[i]]=i;
    }
    for(int i=maxx-1;i>=0;i--){
        if(dd[i]==-1)dd[i]=dd[i+1];
    }
    ed.resize(p[0]+1);
    for(int i=n-2;i>=0;i--){
        if(p[i+1]%p[i]<=p[0])ed[p[i+1]%p[i]].push_back({i,i+1});
        for(int j=2*p[i];j<=maxx;j+=p[i]){
            if(p[dd[j]]%p[i]<=p[0])ed[p[dd[j]]%p[i]].push_back({i,dd[j]});
        }
    }
    for(int i=0;i<n;i++){
        r[i]=i;
        sz[i]=1;
    }
    long long res=0;
    for(int i=0;i<p[0];i++){
        for(ii p:ed[i]){
            int u=Find(p.fi);
            int v=Find(p.se);
            if(u!=v){
                if(sz[u]<sz[v])swap(u,v);
                r[v]=u;
                sz[u]+=sz[v];
                res+=i;
                if(sz[u]==n){
                    cout<<res;
                    return 0;
                }
            }
        }
    }
    cout<<res;
    return 0;
}

Compilation message

sirni.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main()
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 40540 KB Output is correct
2 Correct 52 ms 63412 KB Output is correct
3 Correct 19 ms 39516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 305 ms 176548 KB Output is correct
3 Correct 14 ms 40028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 40028 KB Output is correct
2 Correct 15 ms 39772 KB Output is correct
3 Correct 14 ms 39616 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12060 KB Output is correct
2 Correct 66 ms 23440 KB Output is correct
3 Correct 34 ms 17596 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5464 KB Output is correct
2 Correct 38 ms 16976 KB Output is correct
3 Correct 29 ms 11316 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20256 KB Output is correct
2 Correct 63 ms 23796 KB Output is correct
3 Correct 34 ms 14112 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4292 KB Output is correct
2 Correct 53 ms 24488 KB Output is correct
3 Correct 35 ms 19380 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 48988 KB Output is correct
2 Correct 291 ms 117712 KB Output is correct
3 Correct 58 ms 51324 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47948 KB Output is correct
2 Correct 380 ms 143508 KB Output is correct
3 Correct 104 ms 115552 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41808 KB Output is correct
2 Correct 366 ms 139044 KB Output is correct
3 Correct 35 ms 17716 KB Output is correct