oj.uz

Submission #552597

# Submission time Handle Problem Language Result Execution time Memory
552597 2022-04-23T11:46:30 Z chenwz Sirni (COCI17_sirni) C++11
140 / 140
 3538 ms 535192 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;
  vector<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 114 ms 235088 KB Output is correct
2 Correct 169 ms 236652 KB Output is correct
3 Correct 113 ms 234424 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 729 ms 235420 KB Output is correct
3 Correct 116 ms 235180 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 235156 KB Output is correct
2 Correct 117 ms 234708 KB Output is correct
3 Correct 125 ms 235220 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 34008 KB Output is correct
2 Correct 428 ms 61308 KB Output is correct
3 Correct 179 ms 39344 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 25504 KB Output is correct
2 Correct 185 ms 46324 KB Output is correct
3 Correct 147 ms 22408 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 46368 KB Output is correct
2 Correct 543 ms 76080 KB Output is correct
3 Correct 179 ms 37968 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8516 KB Output is correct
2 Correct 458 ms 70704 KB Output is correct
3 Correct 203 ms 37452 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 247996 KB Output is correct
2 Correct 2546 ms 444716 KB Output is correct
3 Correct 332 ms 250312 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 247784 KB Output is correct
2 Correct 3538 ms 535192 KB Output is correct
3 Correct 438 ms 254412 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 237512 KB Output is correct
2 Correct 3061 ms 530348 KB Output is correct
3 Correct 183 ms 39228 KB Output is correct