oj.uz

Submission #1106918

# Submission time Handle Problem Language Result Execution time Memory
1106918 2024-10-31T09:13:09 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 4601 ms 475440 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 78672 KB Output is correct
2 Correct 47 ms 82276 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 28 ms 41976 KB Output is correct
2 Correct 128 ms 77388 KB Output is correct
3 Correct 13 ms 78672 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 78672 KB Output is correct
2 Correct 11 ms 70224 KB Output is correct
3 Correct 14 ms 78788 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 60876 KB Output is correct
2 Correct 646 ms 97824 KB Output is correct
3 Correct 258 ms 73332 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49652 KB Output is correct
2 Correct 345 ms 98036 KB Output is correct
3 Correct 220 ms 58944 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 97824 KB Output is correct
2 Correct 842 ms 147224 KB Output is correct
3 Correct 245 ms 73312 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 51256 KB Output is correct
2 Correct 853 ms 147056 KB Output is correct
3 Correct 226 ms 73268 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 106048 KB Output is correct
2 Correct 3494 ms 475304 KB Output is correct
3 Correct 249 ms 106084 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 106116 KB Output is correct
2 Correct 4601 ms 475352 KB Output is correct
3 Correct 305 ms 106060 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 82436 KB Output is correct
2 Correct 4488 ms 475440 KB Output is correct
3 Correct 260 ms 73328 KB Output is correct