# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1085112 |
2024-09-07T14:22:10 Z |
fryingduc |
Sirni (COCI17_sirni) |
C++17 |
|
2939 ms |
239952 KB |
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e5 + 5;
const int N = 1e7 + 7;
int n;
vector<int> value[N];
int lab[maxn];
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool is_joined(int u, int v) {
u = find(u), v = find(v);
if(u == v) return 1;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return 0;
}
void solve() {
cin >> n;
vector<int> a;
for(int i = 1; i <= n; ++i) {
int x; cin >> x;
a.push_back(x);
lab[i] = -1;
value[x].push_back(i);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int rem = 0;
long long ans = 0;
while(1) {
for(int i = 0; i < (int)a.size(); ++i) {
for(int j = a[i] + rem; j <= a.back(); j += a[i]) {
if(value[j].empty()) continue;
for(auto pos:value[j]) {
if(!is_joined(value[a[i]][0], pos)) {
// debug(value[a[i]][0], pos, a[i], j);
ans += rem;
}
}
}
}
bool flag = 1;
for(int i = 2; i <= n; ++i) {
if(find(i) != find(1)) {
flag = 0;
break;
}
}
if(flag) {
cout << ans;
return;
}
++rem;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
616 ms |
235316 KB |
Output is correct |
2 |
Correct |
715 ms |
235092 KB |
Output is correct |
3 |
Correct |
434 ms |
235304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
235232 KB |
Output is correct |
2 |
Correct |
613 ms |
235088 KB |
Output is correct |
3 |
Correct |
170 ms |
235168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
575 ms |
235144 KB |
Output is correct |
2 |
Correct |
240 ms |
235092 KB |
Output is correct |
3 |
Correct |
417 ms |
235316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
239648 KB |
Output is correct |
2 |
Correct |
266 ms |
239264 KB |
Output is correct |
3 |
Correct |
150 ms |
238984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
235788 KB |
Output is correct |
2 |
Correct |
213 ms |
237288 KB |
Output is correct |
3 |
Correct |
171 ms |
239056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
260 ms |
239560 KB |
Output is correct |
2 |
Correct |
201 ms |
239564 KB |
Output is correct |
3 |
Correct |
154 ms |
239552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
236752 KB |
Output is correct |
2 |
Correct |
223 ms |
238788 KB |
Output is correct |
3 |
Correct |
160 ms |
239304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
972 ms |
239952 KB |
Output is correct |
2 |
Correct |
727 ms |
239720 KB |
Output is correct |
3 |
Correct |
921 ms |
239816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
239816 KB |
Output is correct |
2 |
Correct |
1715 ms |
239052 KB |
Output is correct |
3 |
Correct |
198 ms |
239660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
894 ms |
236156 KB |
Output is correct |
2 |
Correct |
2939 ms |
238792 KB |
Output is correct |
3 |
Correct |
149 ms |
239304 KB |
Output is correct |