oj.uz

Submission #990842

# Submission time Handle Problem Language Result Execution time Memory
990842 2024-05-31T13:37:41 Z doducanh Sirni (COCI17_sirni) C++14
126 / 140
 783 ms 786432 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+1);
    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(maxx);
    for(int i=n-2;i>=0;i--){
        ed[p[i+1]%p[i]].push_back({i,i+1});
        for(int j=2*p[i];j<=maxx;j+=p[i]){
            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<maxx;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 53 ms 274384 KB Output is correct
2 Correct 103 ms 308484 KB Output is correct
3 Correct 61 ms 273552 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 731 ms 722456 KB Output is correct
3 Correct 56 ms 275124 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 274384 KB Output is correct
2 Correct 55 ms 273748 KB Output is correct
3 Correct 59 ms 274476 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 38876 KB Output is correct
2 Correct 92 ms 70828 KB Output is correct
3 Correct 56 ms 53000 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30216 KB Output is correct
2 Correct 57 ms 52744 KB Output is correct
3 Correct 35 ms 25488 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 50140 KB Output is correct
2 Correct 105 ms 88600 KB Output is correct
3 Correct 55 ms 47984 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9824 KB Output is correct
2 Correct 106 ms 98116 KB Output is correct
3 Correct 50 ms 52360 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 290144 KB Output is correct
2 Correct 727 ms 631960 KB Output is correct
3 Correct 99 ms 293536 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 293856 KB Output is correct
2 Runtime error 783 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 276864 KB Output is correct
2 Correct 768 ms 703908 KB Output is correct
3 Correct 50 ms 52204 KB Output is correct