Submission #712880

#	Time	Username	Problem	Language	Result	Execution time	Memory
712880		Quan2003	Sirni (COCI17_sirni)	C++17	140 / 140	1639 ms	717632 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz=1e7+5;
const int mod=1e9+7;
int n;
long long a[sz];
long long p[sz];
vector<pair<int,int>>edge[sz];
int parent[sz];
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 ;
	  parent[roota] = rootb;
}
int main(){
      cin>>n;
      int bound = 0;
      for(int i = 1; i <= n; i++){
          int x; cin>>x; a[x]++;
          p[x] = x;
          bound = max(bound,x);
      }
      for(int i = bound ; i > 0; i--){
           if(!a[i]) p[i] = p[i+1];
      } 
      for (int i = 1; i <= bound; i++) parent[i] = i;
      for(int i = 1; i <= bound; i++){
           if(!a[i]) continue;
           for(int j = i; j <= bound; j+=i){
                int l = (i == j) ? i + 1: j;
                int rr = min(i + j - 1, bound);
                if(p[l] <= rr) edge[p[l]%i].push_back({p[l],i});
           }
      }
      int ans = 0;
      for(int i = 0; i <= bound; i++){
           for(int j = 0; j < edge[i].size(); j++){
                int u = edge[i][j].first;
                int v = edge[i][j].second;
                if(find(u) == find(v)) continue;
                unite(u,v);
                ans+=i;
           }
      }
      cout<<ans<<endl;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:42:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |            for(int j = 0; j < edge[i].size(); j++){
      |                           ~~^~~~~~~~~~~~~~~~

• 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