oj.uz

Submission #552596

# Submission time Handle Problem Language Result Execution time Memory
552596 2022-04-23T11:42:13 Z chenwz Sirni (COCI17_sirni) C++11
112 / 140
 5000 ms 296724 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;
  set<int> ws;
  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;
      ws.insert(w), maxw = max(w, maxw), EM[w].push_back({i, j});
    }
  }
  long long sw = 0;
  for (int w : ws)
    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 3 ms 980 KB Output is correct
2 Correct 67 ms 3028 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 536 ms 1216 KB Output is correct
3 Correct 6 ms 1236 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 984 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 4 ms 1104 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 10868 KB Output is correct
2 Correct 533 ms 37540 KB Output is correct
3 Correct 262 ms 16048 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2036 KB Output is correct
2 Correct 368 ms 23648 KB Output is correct
3 Correct 190 ms 10700 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 22776 KB Output is correct
2 Correct 684 ms 52000 KB Output is correct
3 Correct 223 ms 14644 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3992 KB Output is correct
2 Correct 656 ms 47180 KB Output is correct
3 Correct 202 ms 14256 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 13336 KB Output is correct
2 Correct 3549 ms 209616 KB Output is correct
3 Correct 261 ms 15632 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 13096 KB Output is correct
2 Execution timed out 5073 ms 296724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2920 KB Output is correct
2 Execution timed out 5090 ms 282264 KB Time limit exceeded
3 Halted 0 ms 0 KB -