oj.uz

Submission #712880

# Submission time Handle Problem Language Result Execution time Memory
712880 2023-03-20T09:39:42 Z Quan2003 Sirni (COCI17_sirni) C++17
140 / 140
 1639 ms 717632 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 259 ms 356492 KB Output is correct
2 Correct 264 ms 356668 KB Output is correct
3 Correct 239 ms 356396 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 235340 KB Output is correct
2 Correct 508 ms 353560 KB Output is correct
3 Correct 253 ms 356724 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 356720 KB Output is correct
2 Correct 239 ms 355276 KB Output is correct
3 Correct 276 ms 356752 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 264836 KB Output is correct
2 Correct 394 ms 292068 KB Output is correct
3 Correct 214 ms 269992 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 256348 KB Output is correct
2 Correct 227 ms 273484 KB Output is correct
3 Correct 189 ms 255152 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 276884 KB Output is correct
2 Correct 309 ms 306668 KB Output is correct
3 Correct 214 ms 268256 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 242396 KB Output is correct
2 Correct 308 ms 301116 KB Output is correct
3 Correct 205 ms 268008 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 443056 KB Output is correct
2 Correct 1275 ms 639204 KB Output is correct
3 Correct 395 ms 445480 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 442912 KB Output is correct
2 Correct 1639 ms 717632 KB Output is correct
3 Correct 395 ms 449124 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 405324 KB Output is correct
2 Correct 1612 ms 690584 KB Output is correct
3 Correct 221 ms 269936 KB Output is correct