Submission #1101143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101143		akamizane	Sirni (COCI17_sirni)	C++17	140 / 140	1322 ms	766620 KiB

sirni

#include<bits/stdc++.h>
 
using namespace std;
 
#define debug(...) 40

 
using ll = long long;
using pii = pair<int,int>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 5;

struct DSU{
  vector<int> par,sz;
  DSU(){};
  DSU(int n){
    par.resize(n);
    iota(all(par), 0);
    sz.resize(n, 1);
  }
  int find (int x){
    return x == par[x] ? x : par[x] = find(par[x]);
  }
  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    par[y] = x;
    return true;
  }
};

void solve(){
 int n;
 cin >> n;
 vector<int> a(n);
 int mx = 0;
 for (auto& x : a){
  cin >> x;
  chmax(mx, x);
 }
 sort(all(a));
 a.erase(unique(all(a)), a.end());
 vector<int> nxt(mx + 1, -1);
 n = a.size();
 REP(i, n){
   nxt[a[i]] = i;
 }
 for (int i = mx - 1; i >= 0; i--){
  if (nxt[i] == -1) nxt[i] = nxt[i + 1];
 }
 vector<pii> ad[mx + 1];
 REP(i, n - 1){
   ad[a[i + 1] % a[i]].pb({i, i + 1});
   for (auto at = 2 * a[i]; at <= mx; at += a[i]){
    int pos = nxt[at];
    ad[a[pos] % a[i]].pb({i, pos});
   }
 }
 ll cost = 0;
 DSU dsu(n);
 FOR(i, 0, mx){
  for (auto [u, v] : ad[i]){
    if (dsu.unite(u, v)) cost += i;
  }
 }
 cout << cost;
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  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