# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1024129 |
2024-07-15T12:58:05 Z |
Thunnus |
Sirni (COCI17_sirni) |
C++17 |
|
894 ms |
786432 KB |
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
struct DSU{
vi size, par;
DSU(int n) : size(n, 1), par(n, -1) {}
int find_set(int a){
return (par[a] == -1 ? a : par[a] = find_set(par[a]));
}
bool unite(int a, int b){
a = find_set(a), b = find_set(b);
if(a == b) return false;
if(size[a] < size[b])
swap(a, b);
par[b] = a;
size[a] += size[b];
return true;
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vi cards(n);
for(int &i : cards)
cin >> i;
sort(cards.begin(), cards.end());
cards.erase(unique(cards.begin(), cards.end()), cards.end());
int largest = cards.back(), cost = 0;
n = sz(cards);
vi next_largest(largest + 1, -1);
for(int i = 0; i < n; i++)
next_largest[cards[i]] = i;
for(int i = largest - 1; i >= 0; i--)
if(next_largest[i] == -1)
next_largest[i] = next_largest[i + 1];
vector<vector<pii>> pos_edges(largest + 1);
for(int i = 0; i < n - 1; i++){
pos_edges[cards[i + 1] % cards[i]].emplace_back(i, i + 1);
for(int at = 2 * cards[i]; at <= largest; at += cards[i]){
int good_mod = next_largest[at];
pos_edges[cards[good_mod] % cards[i]].emplace_back(i, good_mod);
}
}
DSU dsu(n);
for(int i = 0; i <= largest; i++){
for(auto edge : pos_edges[i]){
if(dsu.unite(edge.fi, edge.se))
cost += i;
}
}
cout << cost;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
313416 KB |
Output is correct |
2 |
Correct |
223 ms |
368716 KB |
Output is correct |
3 |
Correct |
150 ms |
312660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Runtime error |
659 ms |
786432 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
313528 KB |
Output is correct |
2 |
Correct |
155 ms |
312916 KB |
Output is correct |
3 |
Correct |
155 ms |
313688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
53704 KB |
Output is correct |
2 |
Correct |
138 ms |
108972 KB |
Output is correct |
3 |
Correct |
82 ms |
74044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
35676 KB |
Output is correct |
2 |
Correct |
89 ms |
77124 KB |
Output is correct |
3 |
Correct |
48 ms |
37852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
76556 KB |
Output is correct |
2 |
Correct |
165 ms |
144876 KB |
Output is correct |
3 |
Correct |
89 ms |
70540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
14236 KB |
Output is correct |
2 |
Correct |
167 ms |
144532 KB |
Output is correct |
3 |
Correct |
80 ms |
72972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
218 ms |
340232 KB |
Output is correct |
2 |
Runtime error |
669 ms |
786432 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
350264 KB |
Output is correct |
2 |
Runtime error |
705 ms |
786432 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
185 ms |
318544 KB |
Output is correct |
2 |
Runtime error |
894 ms |
786432 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |