oj.uz

Submission #1101143

# Submission time Handle Problem Language Result Execution time Memory
1101143 2024-10-15T15:45:44 Z akamizane Sirni (COCI17_sirni) C++17
140 / 140
 1322 ms 766620 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 274136 KB Output is correct
2 Correct 297 ms 302668 KB Output is correct
3 Correct 230 ms 273492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 822 ms 677420 KB Output is correct
3 Correct 237 ms 275056 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 274552 KB Output is correct
2 Correct 225 ms 273740 KB Output is correct
3 Correct 229 ms 274508 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 39044 KB Output is correct
2 Correct 106 ms 74492 KB Output is correct
3 Correct 92 ms 51252 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 29780 KB Output is correct
2 Correct 85 ms 51532 KB Output is correct
3 Correct 51 ms 25940 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 54736 KB Output is correct
2 Correct 141 ms 90320 KB Output is correct
3 Correct 75 ms 49320 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9928 KB Output is correct
2 Correct 142 ms 87564 KB Output is correct
3 Correct 84 ms 51752 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 289132 KB Output is correct
2 Correct 1062 ms 659928 KB Output is correct
3 Correct 360 ms 291736 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 293084 KB Output is correct
2 Correct 1322 ms 766620 KB Output is correct
3 Correct 372 ms 351436 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 276916 KB Output is correct
2 Correct 1203 ms 636868 KB Output is correct
3 Correct 83 ms 54328 KB Output is correct