Submission #493941

#	Time	Username	Problem	Language	Result	Execution time	Memory
493941		dz001	Sirni (COCI17_sirni)	C++11	140 / 140	4996 ms	536408 KiB

sirni

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14