Submission #518430

#	Time	Username	Problem	Language	Result	Execution time	Memory
518430		Alex_tz307	Sirni (COCI17_sirni)	C++17	140 / 140	3477 ms	747000 KiB

sirni

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14