oj.uz

Submission #1106917

# Submission time Handle Problem Language Result Execution time Memory
1106917 2024-10-31T09:12:41 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 4864 ms 475552 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod=1e9+7;
#define fi first
#define se second
int n,u,minn[10000005],pa[10000005];
vector<int> vec;
vector<pair<int,pair<int,int>>> krk;
ll ketqua;
int find_pa(int u)
{
    if (pa[u]==u) return u;
    return pa[u]=find_pa(pa[u]);
}
void Merge(int u,int v,int x)
{
    u=find_pa(u);
    v=find_pa(v);
    if (u==v) return;
    ketqua+=x;
    pa[u]=v;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        cin>>u;
        pa[u]=u;
        vec.push_back(u);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(begin(vec),end(vec)),end(vec));
    for (int i=0;i<=10000001;++i) minn[i]=-1;
    for (int i=vec.size()-1;i>=1;--i)
    {
        for (int j=vec[i];j>vec[i-1];--j) minn[j]=vec[i];
    }
    for (int i=0;i<=vec[0];++i) minn[i]=vec[0];
    for (int i=0;i<vec.size();++i)
    {
        if (vec[i]==0) continue;
        int hao=vec[i];
        for (int j=hao;j<=10000000;j+=hao)
        {
            if (j==hao)
            {
                if (minn[j+1]==-1 || minn[j+1]>j+hao) continue;
                krk.push_back({min(hao%minn[j+1],minn[j+1]%hao),{hao,minn[j+1]}});
            }
            else
            {
                if (minn[j]==-1 || minn[j]>j+hao) continue;
                krk.push_back({min(hao%minn[j],minn[j]%hao),{hao,minn[j]}});
            }
        }
    }
    sort(krk.begin(),krk.end());
    for (int i=0;i<krk.size();++i)
    {
        Merge(krk[i].se.fi,krk[i].se.se,krk[i].fi);
        //cout<<krk[i].se.fi<<" "<<krk[i].se.se<<" "<<krk[i].fi<<'\n';
    }
    cout<<ketqua;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0;i<vec.size();++i)
      |                  ~^~~~~~~~~~~
sirni.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i=0;i<krk.size();++i)
      |                  ~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 78584 KB Output is correct
2 Correct 47 ms 82132 KB Output is correct
3 Correct 13 ms 78864 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 41772 KB Output is correct
2 Correct 144 ms 77304 KB Output is correct
3 Correct 18 ms 78672 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 78576 KB Output is correct
2 Correct 12 ms 70224 KB Output is correct
3 Correct 19 ms 78672 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 61048 KB Output is correct
2 Correct 660 ms 97708 KB Output is correct
3 Correct 278 ms 73260 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49652 KB Output is correct
2 Correct 400 ms 95784 KB Output is correct
3 Correct 262 ms 58808 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 95740 KB Output is correct
2 Correct 907 ms 147080 KB Output is correct
3 Correct 262 ms 73168 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 51260 KB Output is correct
2 Correct 822 ms 147224 KB Output is correct
3 Correct 240 ms 73220 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 106060 KB Output is correct
2 Correct 3482 ms 475396 KB Output is correct
3 Correct 251 ms 106052 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 106044 KB Output is correct
2 Correct 4864 ms 475552 KB Output is correct
3 Correct 299 ms 106180 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 82436 KB Output is correct
2 Correct 4476 ms 475392 KB Output is correct
3 Correct 268 ms 73268 KB Output is correct