# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248577 |
2020-07-12T19:01:05 Z |
Redhood |
Sirni (COCI17_sirni) |
C++14 |
|
288 ms |
287732 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define len(x) (int)(x).size()
#define pb push_back
using namespace std;
typedef pair<int,int > pii;
typedef long long ll;
typedef long double ld;
const int N = 1e5;
int s[N], p[N];
void make(int v){
p[v] = v ;
s[v] = 1;
}
int fin(int v){
if(p[v] == v)return v;
return p[v] = fin(p[v]);
}
void un(int a , int b){
a = fin(a) , b = fin(b);
if(a == b)return;
if(s[a] < s[b])swap(a , b);
p[b] = a , s[a] += s[b];
}
const int NN = (int)1e7 + 1;
int great[NN];
vector<pii> Edges[NN];
signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n;cin >> n;
vector<int>p(n);
for(auto &i : p)cin >> i;
sort(all(p));
p.erase(unique(all(p)) , p.end());
n = len(p);
for(int i = 0 ; i< n; ++i)
make(i);
int lst = n - 1;
for(int j = NN - 1; j >=0 ; --j){
while(lst - 1>= 0 && p[lst - 1] >= j)
--lst;
great[j] = lst;
}
for(int i = 0 ; i < n; ++i){
if(fin(i) == i){
int prev = -1;
for(int j = (p[n-1]/p[i])*p[i]; j >= 0; j -= p[i]){
int cur = great[j];
if(cur == prev)continue;
if(p[cur] == j){
un(i , cur);
}else Edges[p[cur]-j].pb({i , cur});
prev = cur;
}
}
}
ll answer = 0;
for(int i = 0 ;i < NN; ++i){
for(auto u : Edges[i]){
if(fin(u.fi) != fin(u.se)){
un(u.fi , u.se);
answer += i;
}
}
}
cout << answer << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
158 ms |
274424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
163 ms |
274428 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
162 ms |
274424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
217 ms |
282568 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
170 ms |
275960 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
235 ms |
286888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
178 ms |
276576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
281 ms |
287732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
288 ms |
286448 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
189 ms |
276984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |