Submission #1061663

#TimeUsernameProblemLanguageResultExecution timeMemory
1061663dimasnbayuSirni (COCI17_sirni)C++14
98 / 140
1106 ms786432 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int sz=1e5+5; int par[sz],nx[10000005],av[10000005]; vector<int> arr; vector<pair<int,pair<int,int>>> v; int find(int x){ if(par[x]==x) return x; else return par[x]=find(par[x]); } void merge(int x, int y){ x=find(x),y=find(y); par[x]=y; } bool check(int x, int y){ return find(x)==find(y); } signed main(){ int n; cin>>n; for(int i=1;i<=n;i++){ int a; cin>>a; arr.push_back(a); } sort(arr.begin(),arr.end()); arr.erase(unique(arr.begin(),arr.end()), arr.end()); // sort(arr.begin(),arr.end()); for(int i=0;i<arr.size();i++){ par[i]=i; av[arr[i]]=i; } int now=0; for(int i=0;i<=arr.back();i++){ while(now+1<arr.size() && arr[now]<=i) now++; nx[i]=now; // cout<<nx[i]<<" "; } // cout<<endl; for(int i=0;i<arr.size();i++){ // cout<<arr[i]<<" "; for(int j=arr[i];j<=arr.back();j+=arr[i]){ if(i==nx[j]) continue; if(v.size()==0 || ((v.back().second.first!=i || v.back().second.second!=nx[j]))) v.push_back({arr[nx[j]]%arr[i],{i,nx[j]}}); if(arr[av[j]]%arr[i]==0) v.push_back({0,{i,av[j]}}); } } // cout<<endl; sort(v.begin(),v.end()); int ans=0; for(int i=0;i<v.size();i++){ // cout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<endl; if(!check(v[i].second.first,v[i].second.second)){ ans+=v[i].first; merge(v[i].second.first,v[i].second.second); } } cout<<ans; }

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~
sirni.cpp:34:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(now+1<arr.size() && arr[now]<=i) now++;
      |               ~~~~~^~~~~~~~~~~
sirni.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~
sirni.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...