oj.uz

답안 #493941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493941 2021-12-13T12:30:01 Z dz001 Sirni (COCI17_sirni) C++11
140 / 140
 4996 ms 536408 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=1e7+10;
const int N=1e5+10;
vector<pair<int,int>> e[MX];
vector<int> b;
int a[N],par[N],rnk[N];
int n;

int find(int x)
{
  if (par[x] == -1) return x;
  return par[x] = find(par[x]);
}

void join(int a, int b)
{
  a = find(a);
  b = find(b);
  assert(a != b);

  if (rnk[a] > rnk[b]) par[b] = a;
  else if (rnk[b] > rnk[a]) par[a] = b;
  else {
    rnk[a]++;
    par[b] = a;
  }
}

signed main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(nullptr);

    cin>>n;
    int mx=-1;
    for(int i=0;i<n;++i)cin>>a[i],mx=max(mx,a[i]),b.push_back(a[i]);
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());

    long long ans=0;
    for(int i=0;i<b.size();++i){
        par[i]=-1;
        int k=1;
        for(k=1;k*b[i]<=mx;++k){
            if(k==1){
                int j=upper_bound(b.begin(),b.end(),b[i])-b.begin();
                if(j==b.size())continue;
                e[b[j]%b[i]].push_back({i,j});
            }else{
                int j=lower_bound(b.begin(),b.end(),b[i]*k)-b.begin();
                if(j==b.size())continue;
                e[b[j]%b[i]].push_back({i,j});
                while(lower_bound(b.begin(),b.end(),b[i]*(k+1))-b.begin()==j)++k;
                // ++k;
            }
        }
    }
    // for(auto i:e){
    //     cout<<i.first<<' '<<i.second.first<<' '<<i.second.second<<endl;
    // }

    for(int j=0;j<MX;++j){
        for(auto i:e[j]){
            int u=i.first,v=i.second;

            if(find(u)!=find(v)){
                join(u,v);
                ans+=j;
            }
        }
    }
    cout<<ans;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:43:18: 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<b.size();++i){
      |                 ~^~~~~~~~~
sirni.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 if(j==b.size())continue;
      |                    ~^~~~~~~~~~
sirni.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 if(j==b.size())continue;
      |                    ~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 235220 KB Output is correct
2 Correct 194 ms 237640 KB Output is correct
3 Correct 162 ms 235564 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 235256 KB Output is correct
2 Correct 617 ms 235844 KB Output is correct
3 Correct 144 ms 235364 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 235304 KB Output is correct
2 Correct 143 ms 235092 KB Output is correct
3 Correct 151 ms 235332 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 246540 KB Output is correct
2 Correct 746 ms 273320 KB Output is correct
3 Correct 382 ms 251576 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 237012 KB Output is correct
2 Correct 384 ms 258264 KB Output is correct
3 Correct 310 ms 246604 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 520 ms 258600 KB Output is correct
2 Correct 955 ms 288140 KB Output is correct
3 Correct 386 ms 250136 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 239116 KB Output is correct
2 Correct 861 ms 282912 KB Output is correct
3 Correct 364 ms 249660 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 249544 KB Output is correct
2 Correct 3511 ms 444904 KB Output is correct
3 Correct 395 ms 251960 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 249936 KB Output is correct
2 Correct 4996 ms 536408 KB Output is correct
3 Correct 548 ms 255404 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 237908 KB Output is correct
2 Correct 4505 ms 531836 KB Output is correct
3 Correct 404 ms 251436 KB Output is correct