# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
136402 |
2019-07-25T08:40:43 Z |
darkkcyan |
Sirni (COCI17_sirni) |
C++14 |
|
5000 ms |
395232 KB |
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;
// #define rand __rand
// mt19937 rand(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
#define llong long long
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
template<class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
#define maxn 101010
int n;
int a[maxn];
int dsu[maxn];
int n_set;
int findp(int u) { return u == dsu[u] ? u : dsu[u] = findp(dsu[u]); }
void join(int u, int v) {
u = findp(u);
v = findp(v);
if (u == v) return ;
if (rand() & 1) swap(u, v);
dsu[u] = v;
--n_set;
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
rep(i, n) cin >> a[i];
sort(a, a + n);
n = (int)(unique(a, a + n) - a);
min_priority_queue<tuple<int, int, int>> pq;
rep(i, n) {
for (int k = 1; k * a[i] <= a[n - 1]; ++k) {
auto t = lower_bound(a, a + n, k * a[i]) - a;
if (t != n and a[t] == a[i]) ++t;
if (t == n) break;
pq.push({a[t] % a[i], i, t});
k = a[t] / a[i];
}
}
// clog << "nice" << endl;
n_set = n;
rep1(i, n) dsu[i] = i;
llong ans = 0;
while (n_set != 1) {
int cost, src, cur;
tie(cost, src, cur) = pq.top();
pq.pop();
if (findp(src) != findp(cur)) {
ans += cost;
join(src, cur);
}
int div = a[cur] / a[src];
++cur;
if (cur == n or a[cur] / a[src] != div) continue;
pq.push({a[cur] % a[src], src, cur});
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
26 ms |
3560 KB |
Output is correct |
3 |
Correct |
5 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
1268 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
4 ms |
568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
544 ms |
13380 KB |
Output is correct |
2 |
Correct |
1297 ms |
50220 KB |
Output is correct |
3 |
Correct |
286 ms |
25736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
3688 KB |
Output is correct |
2 |
Correct |
346 ms |
50380 KB |
Output is correct |
3 |
Correct |
550 ms |
13636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1062 ms |
50460 KB |
Output is correct |
2 |
Correct |
1033 ms |
99608 KB |
Output is correct |
3 |
Correct |
299 ms |
25692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
6852 KB |
Output is correct |
2 |
Correct |
1043 ms |
99620 KB |
Output is correct |
3 |
Correct |
273 ms |
25672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
572 ms |
25708 KB |
Output is correct |
2 |
Correct |
3306 ms |
394864 KB |
Output is correct |
3 |
Correct |
592 ms |
25804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
320 ms |
25800 KB |
Output is correct |
2 |
Execution timed out |
5082 ms |
395232 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
3816 KB |
Output is correct |
2 |
Execution timed out |
5117 ms |
395196 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |