# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
136387 |
2019-07-25T08:12:48 Z |
darkkcyan |
Sirni (COCI17_sirni) |
C++14 |
|
5000 ms |
395700 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 or a[t] / a[i] != k) continue;
pq.push({a[t] % a[i], i, t});
}
}
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 |
92 ms |
3688 KB |
Output is correct |
3 |
Correct |
5 ms |
696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
520 KB |
Output is correct |
2 |
Correct |
948 ms |
1308 KB |
Output is correct |
3 |
Correct |
5 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 |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
500 ms |
13868 KB |
Output is correct |
2 |
Correct |
1309 ms |
50652 KB |
Output is correct |
3 |
Correct |
331 ms |
26168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
3644 KB |
Output is correct |
2 |
Correct |
349 ms |
50572 KB |
Output is correct |
3 |
Correct |
502 ms |
14024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1040 ms |
50760 KB |
Output is correct |
2 |
Correct |
1063 ms |
100172 KB |
Output is correct |
3 |
Correct |
329 ms |
26312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
7008 KB |
Output is correct |
2 |
Correct |
1084 ms |
100020 KB |
Output is correct |
3 |
Correct |
316 ms |
26176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
576 ms |
26440 KB |
Output is correct |
2 |
Correct |
4049 ms |
395688 KB |
Output is correct |
3 |
Correct |
628 ms |
26256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
351 ms |
26308 KB |
Output is correct |
2 |
Execution timed out |
5126 ms |
395700 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
3816 KB |
Output is correct |
2 |
Execution timed out |
5048 ms |
395528 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |