oj.uz

Submission #990845

# Submission time Handle Problem Language Result Execution time Memory
990845 2024-05-31T13:41:04 Z doducanh Sirni (COCI17_sirni) C++14
126 / 140
 873 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+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(maxx+7);
    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 274220 KB Output is correct
2 Correct 105 ms 308304 KB Output is correct
3 Correct 54 ms 273724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 781 ms 726276 KB Output is correct
3 Correct 59 ms 275028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 274260 KB Output is correct
2 Correct 53 ms 273744 KB Output is correct
3 Correct 62 ms 274488 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38408 KB Output is correct
2 Correct 79 ms 72116 KB Output is correct
3 Correct 53 ms 53468 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30040 KB Output is correct
2 Correct 49 ms 52412 KB Output is correct
3 Correct 38 ms 24976 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 49696 KB Output is correct
2 Correct 105 ms 87636 KB Output is correct
3 Correct 51 ms 46028 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9568 KB Output is correct
2 Correct 109 ms 99320 KB Output is correct
3 Correct 57 ms 52344 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 289360 KB Output is correct
2 Correct 692 ms 636636 KB Output is correct
3 Correct 96 ms 292768 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 293092 KB Output is correct
2 Runtime error 873 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 58 ms 276816 KB Output is correct
2 Correct 838 ms 703628 KB Output is correct
3 Correct 63 ms 53480 KB Output is correct