Submission #657174

#	Time	Username	Problem	Language	Result	Execution time	Memory
657174		Quan2003	Sirni (COCI17_sirni)	C++17	14 / 140	1959 ms	786432 KiB

sirni

#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef long long ll;
const int sz=1e5+1;
const int inf=1e7+5;
int n,m,src,cnt,ans;
int a[sz];
int timer;
int dp[sz];
int d[sz];
int parent[sz];
int compsize[sz];
vector<pair<int,int>>arr;
vector<array<int,3>>edge;
bool vis[sz];
struct cmp {
 bool operator()(const pair<int,int>& value,
        const int& key)
 {
  return (value.first < key);
 }
 bool operator()(const int& key,
     const pair<int,int>& value)
 {
  return (key < value.first);
 }
};
void init(int n){
	for (int i = 1; i <= n; i++){
		   parent[i] = i;
		   compsize[i] = 1;
	  }
}
int find(int a){
	   if (a == parent[a]) return a;
	   return parent[a] = find(parent[a]);
}
void unite(int a, int b){
	  int roota = find(a), rootb = find(b);
	  if (roota == rootb) return ;
	  if (compsize[roota] > compsize[rootb]) swap(roota, rootb);
	  parent[roota] = rootb;
	  compsize[rootb] += compsize[roota];
}
int main(){
      cin>>n;
      int mx = 0;
      for(int i=1;i<=n;i++){
           cin>>a[i];
           mx = max(mx,a[i]);
           arr.push_back({a[i],i});
      }
      sort(arr.begin(),arr.end());
      if(arr[0].first==1){
           cout<<0<<endl;
           return 0; 
      }
      for(int i=0;i<arr.size();i++){
           int j = i+1;
           while (j<n and arr[i].first==arr[j].first){
                unite(arr[i].second,arr[j].second);
                j++;
           }
      }
      arr.erase(unique(arr.begin(),arr.end()),arr.end());
      for(int i = 0 ;i <= n; i++) d[i]=inf;
      for(int i=0;i<arr.size();i++){
           int v = arr[i].first;
           for(int j =v; j<=mx;j+=v){
                int lpos = lower_bound(arr.begin(),arr.end(),j,cmp())-arr.begin();
                if(lpos == i and lpos<arr.size()-1) lpos++; 
                edge.push_back({arr[lpos].first%v,arr[i].second,arr[lpos].second});
                if(arr[lpos].first%v<d[lpos]){
                     d[lpos]=arr[lpos].first%v;
                     dp[lpos]=arr[i].second;
                }
           }
      }
      for(int i = 1; i< arr.size(); i++){
           if(!dp[i]) dp[i]=dp[i-1];
           int u=dp[i]; int v=arr[i].second;
           int w = arr[i].first % a[u];
           edge.push_back({w,u,v});
      }
      init(n);
      sort(edge.begin(),edge.end());
      for(int i=0;i<edge.size();i++){
            int u = edge[i][2]; int v = edge[i][1];
            int w = edge[i][0];
            if(find(u) == find(v)) continue;
            //cout<<u<<' '<<v<<' '<<w<<endl; 
            unite(u,v);
            ans+=w;
      }
      cout<<ans<<endl;  
} 

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       for(int i=0;i<arr.size();i++){
      |                   ~^~~~~~~~~~~
sirni.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |       for(int i=0;i<arr.size();i++){
      |                   ~^~~~~~~~~~~
sirni.cpp:73:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 if(lpos == i and lpos<arr.size()-1) lpos++;
      |                                  ~~~~^~~~~~~~~~~~~
sirni.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       for(int i = 1; i< arr.size(); i++){
      |                      ~^~~~~~~~~~~~
sirni.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |       for(int i=0;i<edge.size();i++){
      |                   ~^~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14