# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1042600 |
2024-08-03T08:19:05 Z |
Abito |
Sirni (COCI17_sirni) |
C++17 |
|
5000 ms |
786432 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=1e7+5;
int a[N],n,par[N],sz[N];
int getpar(int x){
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
void link(int x,int y){
x=getpar(x);
y=getpar(y);
if (x==y) return;
if (sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x];
par[x]=y;
return;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i],par[i]=i,sz[i]=1;
sort(a+1,a+1+n);
vector<vector<int>> v;
for (int i=1;i<n;i++){
v.pb({a[i+1]%a[i],i,i+1});
for (int j=a[i]*2;j<N;j+=i){
int l=1,r=n,mid,idx=-1;
while (l<=r){
mid=(l+r)/2;
if (a[mid]>=j){
idx=mid;
r=mid-1;
}else l=mid+1;
}
if (idx==-1) break;
v.pb({a[idx]%a[i],i,idx});
}
}int ans=0;
sort(v.begin(),v.end());
for (auto u:v){
int x=getpar(u[1]),y=getpar(u[2]);
if (x==y) continue;
ans+=u[0];
link(x,y);
}cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
660 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
5648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
616 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4746 ms |
658792 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2560 ms |
657376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5021 ms |
658852 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
649 ms |
108948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
718 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
732 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
664 ms |
786432 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |