Submission #1193350

#TimeUsernameProblemLanguageResultExecution timeMemory
1193350zyadhanySirni (COCI17_sirni)C++20
98 / 140
2272 ms851968 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll long long #define ld long double #define pl pair<ll, ll> #define vi vector<ll> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "-1\n"; return;} const int MODE = 1e9 + 7; using namespace std; const int MXN = 1e6+10; int PAR[MXN], R[MXN]; ll get(ll n) { if (n == PAR[n]) return n; return PAR[n]=get(PAR[n]); } bool add(ll u, ll v) { u = get(u), v = get(v); if (u == v) return 0; if (R[v] > R[u]) swap(u,v); R[u] += (R[v] == R[u]); PAR[v] = u; return 1; } void INIT() { for (int i = 0; i < MXN; i++) { PAR[i] = i; R[i] = 0; } } void solve(int tc) { ll n; cin >> n; vi X(n); for (int i = 0; i < n; i++) { cin >> X[i]; } set st(all(X)); X.assign(all(st)); n = X.size(); vii E; for (int i = 0; i < n; i++) { if (i) { E.push_back({X[i]%X[i-1], i, i-1}); } for (int j = 2*X[i]; j <= X.back(); j+=X[i]) { ll re = lower_bound(all(X), j) - X.begin(); if (re < X.size() && X[re] < j + X[i]) { E.push_back({X[re]%X[i], i, re}); } } } sortx(E); INIT(); ll res = 0; for (auto e : E) { if (add(e[1], e[2])) res += e[0]; } cout << res << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; // freopen("math.in", "r", stdin); //freopen("output.txt", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...