Submission #872936

#TimeUsernameProblemLanguageResultExecution timeMemory
872936qthang2k11Sirni (COCI17_sirni)C++17
140 / 140
1637 ms652360 KiB
// [+] #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5 + 5, MAX = 1e7 + 5; int n, a[N], mx = 0; vector<pair<int, int>> edges[MAX]; int nxt[MAX]; int p[MAX], num[MAX]; inline int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } bool join(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (num[x] < num[y]) swap(x, y); num[x] += num[y]; p[y] = x; return true; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], mx = max(a[i], mx); iota(p + 1, p + mx + 1, 1); fill(num + 1, num + mx + 1, 1); sort(a + 1, a + n + 1); n = unique(a + 1, a + n + 1) - a - 1; memset(nxt, 63, sizeof nxt); for (int i = 1; i <= n; i++) nxt[a[i]] = a[i]; for (int i = mx; i > 0; i--) nxt[i] = min(nxt[i], nxt[i + 1]); for (int i = 1; i <= n; i++) { if (nxt[a[i] + 1] < a[i] * 2) edges[nxt[a[i] + 1] - a[i]].emplace_back(nxt[a[i] + 1], a[i]); for (int j = a[i] * 2; j <= mx; j += a[i]) if (nxt[j] < j + a[i]) edges[nxt[j] - j].emplace_back(a[i], nxt[j]); } ll ans = 0; for (int i = 0; i < mx; i++) for (const auto &elem: edges[i]) if (join(elem.first, elem.second)) ans += i; cout << ans; return 0; }
#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...