oj.uz

Submission #518430

# Submission time Handle Problem Language Result Execution time Memory
518430 2022-01-23T19:35:35 Z Alex_tz307 Sirni (COCI17_sirni) C++17
140 / 140
 3477 ms 747000 KB 
#include <bits/stdc++.h>

using namespace std;

const int M = 1e7;

struct DSU {
  vector<int> p, sz;

  DSU(int n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[y] < sz[x]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
};

void testCase() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end()); /// pot elimina duplicatele pentru ca le pot unii gratis
  n = a.size();
  vector<int> next(M + 2, -1); /// next[x] = index-ul din a al celei mai mici valori >= x
  int p = n - 1;
  for (int i = M; i > 0; --i) {
    next[i] = next[i + 1];
    while (p >= 0 && a[p] > i) {
      p -= 1;
    }
    if (p >= 0 && a[p] == i) {
      next[i] = p;
    }
  }
  vector<vector<pair<int, int>>> edges(M);
  for (int i = 0; i < n; ++i) {
    if (next[a[i] + 1] != -1) {
      edges[a[next[a[i] + 1]] % a[i]].emplace_back(i, next[a[i] + 1]);
    }
    for (int j = 2 * a[i]; j <= M; j += a[i]) {
      if (next[j] != -1) {
        edges[a[next[j]] % a[i]].emplace_back(i, next[j]);
      }
    }
  }
  int64_t ans = 0;
  int cnt = 0;
  DSU dsu(n);
  for (int w = 0; w < M; ++w) {
    for (auto it : edges[w]) {
      if (dsu.unite(it.first, it.second)) {
        ans += w;
        cnt += 1;
        if (cnt == n - 1) {
          cout << ans << '\n';
          return;
        }
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 274376 KB Output is correct
2 Correct 235 ms 303652 KB Output is correct
3 Correct 150 ms 274632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 274392 KB Output is correct
2 Correct 1364 ms 669052 KB Output is correct
3 Correct 164 ms 275120 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 274356 KB Output is correct
2 Correct 153 ms 274256 KB Output is correct
3 Correct 152 ms 274620 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 285540 KB Output is correct
2 Correct 649 ms 313464 KB Output is correct
3 Correct 349 ms 296068 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 276472 KB Output is correct
2 Correct 595 ms 297916 KB Output is correct
3 Correct 366 ms 285592 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 297044 KB Output is correct
2 Correct 755 ms 330544 KB Output is correct
3 Correct 344 ms 293896 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 278264 KB Output is correct
2 Correct 900 ms 331396 KB Output is correct
3 Correct 332 ms 295696 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 289112 KB Output is correct
2 Correct 1700 ms 633200 KB Output is correct
3 Correct 298 ms 291812 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 293088 KB Output is correct
2 Correct 3401 ms 747000 KB Output is correct
3 Correct 464 ms 348424 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 276840 KB Output is correct
2 Correct 3477 ms 634844 KB Output is correct
3 Correct 366 ms 297768 KB Output is correct