제출 #949169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949169		vjudge1	Sirni (COCI17_sirni)	C++17	42 / 140	596 ms	786432 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S& a, const T& b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
	return a < b ? (a = b) == b : false;
}

struct DSU {
  vector<int> p;
  DSU(int n) {
    p.resize(n);
    iota(all(p), 0ll);
  }
  int find_set(int v) {
    return p[v] == v ? v : p[v] = find_set(p[v]);
  }
  void unite(int u, int v) {
    p[u] = v;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n; cin >> n;
  int a[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  DSU g(n);
  vector<array<int, 3>> edge;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      edge.push_back({min(a[i] % a[j], a[j] % a[i]), i, j});
    }
  }
  sort(all(edge));
  int res = 0;
  for (auto [c, a, b] : edge) {
    a = g.find_set(a), b = g.find_set(b);
    if (a == b) continue;
    g.unite(a, b);
    res += c;
  }
  cout << res;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14