oj.uz

Submission #552595

# Submission time Handle Problem Language Result Execution time Memory
552595 2022-04-23T11:40:29 Z chenwz Sirni (COCI17_sirni) C++11
140 / 140
 3930 ms 301180 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;

  unordered_map<int, vector<pair<int, int>>> EM;
  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});
      // es.push_back({i, j, P[j] % p});
    }
  }
  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;
    }
  }

  // sort(es.begin(), es.end());
  // for (const Edge& e : es) {
  //   int u = find_set(e.u), v = find_set(e.v);
  //   if (u != v) sw += e.w, pa[u] = v;
  // }
  cout << sw << endl;
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4324 KB Output is correct
2 Correct 75 ms 10848 KB Output is correct
3 Correct 11 ms 4964 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 626 ms 33608 KB Output is correct
3 Correct 9 ms 4800 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4068 KB Output is correct
2 Correct 83 ms 64624 KB Output is correct
3 Correct 11 ms 6496 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 11364 KB Output is correct
2 Correct 470 ms 38100 KB Output is correct
3 Correct 182 ms 16672 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2100 KB Output is correct
2 Correct 231 ms 23696 KB Output is correct
3 Correct 135 ms 11204 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 23452 KB Output is correct
2 Correct 597 ms 52608 KB Output is correct
3 Correct 188 ms 15056 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4096 KB Output is correct
2 Correct 525 ms 47564 KB Output is correct
3 Correct 180 ms 14736 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 13708 KB Output is correct
2 Correct 2764 ms 210068 KB Output is correct
3 Correct 195 ms 16408 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 13808 KB Output is correct
2 Correct 3930 ms 301180 KB Output is correct
3 Correct 357 ms 20196 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3020 KB Output is correct
2 Correct 3794 ms 296488 KB Output is correct
3 Correct 204 ms 16636 KB Output is correct