oj.uz

Submission #551571

# Submission time Handle Problem Language Result Execution time Memory
551571 2022-04-21T04:52:23 Z chenwz Sirni (COCI17_sirni) C++11
140 / 140
 4989 ms 395436 KB 
// [COCI2016-2017#6] Sirni
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 4;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
int P[NN], pa[NN];
int find_set(int x) { return pa[x] == x ? x : pa[x] = find_set(pa[x]); }
struct Edge {
  int u, v, w;
  bool operator<(const Edge& e) const { return w < e.w; }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  vector<Edge> es;
  int n;
  cin >> n;
  _for(i, 0, n) cin >> P[i], pa[i] = i;
  sort(P, P + n), n = unique(P, P + n) - P;
  long long ans = 0;
  _for(i, 0, n) for (int x = P[i], y = x; y <= P[n - 1]; y += x) {
    int k = lower_bound(P + i + 1, P + n, y) - P;
    if (k < n && P[k] / x == y / x) es.push_back({i, k, P[k] % x});
  }
  sort(es.begin(), es.end());
  for (const Edge& e : es) {
    int u = find_set(e.u), v = find_set(e.v);
    if (u != v) ans += e.w, pa[u] = v;
  }
  cout << ans << endl;
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 66 ms 3520 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 714 ms 1176 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 532 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 13480 KB Output is correct
2 Correct 583 ms 50440 KB Output is correct
3 Correct 227 ms 25756 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3560 KB Output is correct
2 Correct 285 ms 50436 KB Output is correct
3 Correct 162 ms 13420 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 50452 KB Output is correct
2 Correct 753 ms 99912 KB Output is correct
3 Correct 224 ms 25788 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6812 KB Output is correct
2 Correct 699 ms 99676 KB Output is correct
3 Correct 214 ms 25756 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 25772 KB Output is correct
2 Correct 3548 ms 395436 KB Output is correct
3 Correct 254 ms 25760 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 25764 KB Output is correct
2 Correct 4989 ms 395368 KB Output is correct
3 Correct 407 ms 25744 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3700 KB Output is correct
2 Correct 4788 ms 395192 KB Output is correct
3 Correct 241 ms 25760 KB Output is correct