oj.uz

답안 #1106910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106910 2024-10-31T09:06:49 Z vjudge1 Sirni (COCI17_sirni) C++17
0 / 140
 375 ms 106048 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 (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:54: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]
   54 |     for (int i=0;i<krk.size();++i)
      |                  ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 41768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 78672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 184 ms 60928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 49652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 375 ms 97824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 108 ms 51260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 190 ms 106036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 182 ms 106048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 82436 KB Output isn't correct
2 Halted 0 ms 0 KB -