oj.uz

Submission #949169

# Submission time Handle Problem Language Result Execution time Memory
949169 2024-03-19T03:14:24 Z vjudge1 Sirni (COCI17_sirni) C++17
42 / 140
 596 ms 786432 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14836 KB Output is correct
2 Correct 66 ms 13252 KB Output is correct
3 Correct 58 ms 12744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 14280 KB Output is correct
2 Correct 79 ms 14532 KB Output is correct
3 Correct 60 ms 13252 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 14532 KB Output is correct
2 Correct 58 ms 14788 KB Output is correct
3 Correct 59 ms 13252 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 596 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 507 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 505 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 564 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 491 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 482 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 481 ms 786432 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -