Submission #657179

#	Time	Username	Problem	Language	Result	Execution time	Memory
657179		Quan2003	Sirni (COCI17_sirni)	C++17	140 / 140	1659 ms	690480 KiB

sirni

#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef long long ll;
const int sz=1e7+5;
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>>adj[sz];
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++){
           int x;cin>>x; 
           a[x]++, d[x]=x;
           mx = max(mx,x);
      }
      for(int i=mx-1;i>=0;i--){
          if(!a[i]) d[i]=d[i+1];
      }
      for(int i=1;i<=mx;i++){
           if(!a[i]) continue;
           for(int j=i;j<=mx;j+=i){
                int l = (i==j)? i+1:j;
                int rr = min(i+j-1,mx);
                //cout<<l<<' '<<rr<<' '<<d[l]<<' '<<i<<endl; 
                if(rr >= d[l]) adj[d[l]%i].push_back({d[l],i});
           }    
      }
      init(mx);
      for(int i=0;i<=mx;i++){
           for(int j=0;j<adj[i].size();j++){
                pair<int,int>x=adj[i][j];
                int u=x.first;
                int v=x.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:55:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |            for(int j=0;j<adj[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