oj.uz

Submission #552598

# Submission time Handle Problem Language Result Execution time Memory
552598 2022-04-23T11:49:07 Z chenwz Sirni (COCI17_sirni) C++11
140 / 140
 3590 ms 535156 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);
  int n;
  cin >> n;
  _for(i, 0, n) cin >> P[i], pa[i] = i;
  sort(P, P + n), n = unique(P, P + n) - P;
  valarray<vector<pair<int, int>>> EM(P[n - 1] + 1);
  int maxw = -1;
  _for(i, 0, n) for (int p = P[i], k = 1; k * p <= P[n - 1]; ++k) {
    int j = lower_bound(P + i + 1, P + n, k * p) - P;
    if (j < n && P[j] / p == k) {
      int w = P[j] % p;
      maxw = max(w, maxw), EM[w].push_back({i, j});
    }
  }
  long long sw = 0;
  for (int w = 0; w <= maxw; w++)
    for (const auto& e : EM[w]) {
      int u = find_set(e.first), v = find_set(e.second);
      if (u != v) sw += w, pa[u] = v;
    }
  cout << sw << endl;
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 235068 KB Output is correct
2 Correct 172 ms 236596 KB Output is correct
3 Correct 107 ms 234440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 733 ms 235488 KB Output is correct
3 Correct 107 ms 235216 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 235308 KB Output is correct
2 Correct 108 ms 234628 KB Output is correct
3 Correct 114 ms 235228 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 34040 KB Output is correct
2 Correct 415 ms 61228 KB Output is correct
3 Correct 216 ms 39364 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25420 KB Output is correct
2 Correct 180 ms 46320 KB Output is correct
3 Correct 130 ms 22452 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 46336 KB Output is correct
2 Correct 535 ms 76008 KB Output is correct
3 Correct 180 ms 37980 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8528 KB Output is correct
2 Correct 495 ms 70604 KB Output is correct
3 Correct 184 ms 37580 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 247928 KB Output is correct
2 Correct 2680 ms 444724 KB Output is correct
3 Correct 285 ms 250184 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 247800 KB Output is correct
2 Correct 3590 ms 535156 KB Output is correct
3 Correct 428 ms 254156 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 237460 KB Output is correct
2 Correct 3193 ms 530376 KB Output is correct
3 Correct 191 ms 39360 KB Output is correct