oj.uz

Submission #669206

# Submission time Handle Problem Language Result Execution time Memory
669206 2022-12-06T03:20:37 Z Quan2003 Sirni (COCI17_sirni) C++17
140 / 140
 1686 ms 716868 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 356344 KB Output is correct
2 Correct 265 ms 356660 KB Output is correct
3 Correct 218 ms 356288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 235324 KB Output is correct
2 Correct 504 ms 353536 KB Output is correct
3 Correct 222 ms 356932 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 356652 KB Output is correct
2 Correct 215 ms 355408 KB Output is correct
3 Correct 218 ms 356716 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 264448 KB Output is correct
2 Correct 277 ms 292036 KB Output is correct
3 Correct 199 ms 269900 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 256312 KB Output is correct
2 Correct 216 ms 273392 KB Output is correct
3 Correct 179 ms 255048 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 276488 KB Output is correct
2 Correct 305 ms 306752 KB Output is correct
3 Correct 203 ms 268204 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 242436 KB Output is correct
2 Correct 321 ms 301048 KB Output is correct
3 Correct 197 ms 268088 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 442536 KB Output is correct
2 Correct 1214 ms 639132 KB Output is correct
3 Correct 377 ms 445312 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 442380 KB Output is correct
2 Correct 1686 ms 716868 KB Output is correct
3 Correct 382 ms 448420 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 405036 KB Output is correct
2 Correct 1672 ms 689940 KB Output is correct
3 Correct 202 ms 269196 KB Output is correct