oj.uz

Submission #667244

# Submission time Handle Problem Language Result Execution time Memory
667244 2022-11-30T21:42:36 Z kirakaminski968 Sirni (COCI17_sirni) C++11
140 / 140
 3293 ms 726548 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
const int N = 1e7+100;
struct DSU {
  vi e; void init(int N) { e = vi(N,-1); }
  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
  bool sameSet(int a, int b) { return get(a) == get(b); }
  int size(int x) { return -e[get(x)]; }
  bool unite(int x, int y) { // union by size
    x = get(x), y = get(y); if (x == y) return 0;
    if (e[x] > e[y]) swap(x,y);
    e[x] += e[y]; e[y] = x; return 1;
  }
};
int n;
vector<int> v(N), a;
vector<array<int, 3>> edges[N];
void solve(){
  cin >> n;
  a.resize(n);
  for(int i = 0; i < n; ++i) cin >> a[i];
  DSU d; 
  d.init(n); 
  sort(a.begin(),a.end()); 
  a.resize(unique(a.begin(),a.end()) - a.begin());    
  n = a.size();
  for(int i = 0; i < n - 1; ++i){
    for(int j = a[i]; j <= a.back(); j += a[i]){
      int k = lower_bound(a.begin() + i + 1, a.end(), j) - a.begin();
      if(k >= n || a[k] - j > a[i]) continue;
      edges[a[k] - j].push_back({a[k] - j, k, i});
      }
  }
  ll ans = 0;
  for(int i = 0; i < N; ++i)
    for(auto v: edges[i]){
      if(d.unite(v[1],v[2])){
        ans += v[0];
      }
    }
  cout << ans;
}
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  solve(); 
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 274412 KB Output is correct
2 Correct 172 ms 277976 KB Output is correct
3 Correct 138 ms 274596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 274440 KB Output is correct
2 Correct 546 ms 275460 KB Output is correct
3 Correct 141 ms 274508 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 274392 KB Output is correct
2 Correct 137 ms 274232 KB Output is correct
3 Correct 148 ms 274548 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 289344 KB Output is correct
2 Correct 531 ms 329632 KB Output is correct
3 Correct 298 ms 298624 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 276848 KB Output is correct
2 Correct 287 ms 307496 KB Output is correct
3 Correct 246 ms 289560 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 308976 KB Output is correct
2 Correct 640 ms 352892 KB Output is correct
3 Correct 295 ms 296116 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 279504 KB Output is correct
2 Correct 576 ms 346516 KB Output is correct
3 Correct 304 ms 296296 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 293408 KB Output is correct
2 Correct 2349 ms 586252 KB Output is correct
3 Correct 297 ms 296928 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 293236 KB Output is correct
2 Correct 3293 ms 726548 KB Output is correct
3 Correct 433 ms 303196 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 277792 KB Output is correct
2 Correct 2999 ms 717112 KB Output is correct
3 Correct 310 ms 298228 KB Output is correct