Submission #667244

#	Time	Username	Problem	Language	Result	Execution time	Memory
667244		kirakaminski968	Sirni (COCI17_sirni)	C++11	140 / 140	3293 ms	726548 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
const int N = 1e7+100;
struct DSU {
  vi e; void init(int N) { e = vi(N,-1); }
  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
  bool sameSet(int a, int b) { return get(a) == get(b); }
  int size(int x) { return -e[get(x)]; }
  bool unite(int x, int y) { // union by size
    x = get(x), y = get(y); if (x == y) return 0;
    if (e[x] > e[y]) swap(x,y);
    e[x] += e[y]; e[y] = x; return 1;
  }
};
int n;
vector<int> v(N), a;
vector<array<int, 3>> edges[N];
void solve(){
  cin >> n;
  a.resize(n);
  for(int i = 0; i < n; ++i) cin >> a[i];
  DSU d; 
  d.init(n); 
  sort(a.begin(),a.end()); 
  a.resize(unique(a.begin(),a.end()) - a.begin());    
  n = a.size();
  for(int i = 0; i < n - 1; ++i){
    for(int j = a[i]; j <= a.back(); j += a[i]){
      int k = lower_bound(a.begin() + i + 1, a.end(), j) - a.begin();
      if(k >= n || a[k] - j > a[i]) continue;
      edges[a[k] - j].push_back({a[k] - j, k, i});
      }
  }
  ll ans = 0;
  for(int i = 0; i < N; ++i)
    for(auto v: edges[i]){
      if(d.unite(v[1],v[2])){
        ans += v[0];
      }
    }
  cout << ans;
}
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  solve(); 
  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