| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 852770 |
2023-09-22T16:37:41 Z |
hqminhuwu |
Sirni (COCI17_sirni) |
C++17 |
|
1316 ms |
769468 KB |
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 1e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
int par[N],sz[N];
int get (int u){
if (u == par[u])
return u;
return par[u] = get(par[u]);
}
void update (int u, int v){
if (sz[u] < sz[v])
swap(u,v);
par[v] = u;
sz[u] += sz[v];
}
int n,i,a[N],f[10000002];
vector <pii> v[10000002];
ll ans;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
forr (i,1,n)
cin >> a[i];
sort(a + 1, a + 1 + n);
forr (i,1,n){
if (a[i] != a[i + 1])
f[a[i]] = i;
par[i] = i;
sz[i] = 1;
}
ford (i,10000000,1)
if (!f[i])
f[i] = f[i + 1];
forr (i,1,n){
if (a[i] == a[i + 1])
continue;
int cur = 2 * a[i];
if (i < n)
v[a[i + 1] % a[i]].pb({i,f[a[i + 1]]});
while (cur <= 10000000){
if (!f[cur])
break;
v[a[f[cur]] % a[i]].pb({i,f[cur]});
cur += a[i];
}
}
forr (i,0,10000000)
for (pii k : v[i]){
int p = get(k.st), q = get (k.nd);
if (p != q)
update(p,q), ans += i;
}
cout << ans << "\n";
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
275740 KB |
Output is correct |
| 2 |
Correct |
150 ms |
304976 KB |
Output is correct |
| 3 |
Correct |
101 ms |
275792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
275536 KB |
Output is correct |
| 2 |
Correct |
735 ms |
685720 KB |
Output is correct |
| 3 |
Correct |
102 ms |
276308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
275600 KB |
Output is correct |
| 2 |
Correct |
102 ms |
275536 KB |
Output is correct |
| 3 |
Correct |
104 ms |
275592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
286044 KB |
Output is correct |
| 2 |
Correct |
190 ms |
316660 KB |
Output is correct |
| 3 |
Correct |
156 ms |
299036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
277604 KB |
Output is correct |
| 2 |
Correct |
162 ms |
298928 KB |
Output is correct |
| 3 |
Correct |
146 ms |
285764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
297820 KB |
Output is correct |
| 2 |
Correct |
213 ms |
336496 KB |
Output is correct |
| 3 |
Correct |
154 ms |
294912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
279028 KB |
Output is correct |
| 2 |
Correct |
219 ms |
333600 KB |
Output is correct |
| 3 |
Correct |
154 ms |
300088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
289092 KB |
Output is correct |
| 2 |
Correct |
803 ms |
652748 KB |
Output is correct |
| 3 |
Correct |
158 ms |
291932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
293604 KB |
Output is correct |
| 2 |
Correct |
1316 ms |
769468 KB |
Output is correct |
| 3 |
Correct |
246 ms |
350448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
277840 KB |
Output is correct |
| 2 |
Correct |
1259 ms |
635648 KB |
Output is correct |
| 3 |
Correct |
157 ms |
299584 KB |
Output is correct |
