# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
482396 | 2021-10-24T11:48:13 Z | MilosMilutinovic | Sirni (COCI17_sirni) | C++14 | 1632 ms | 786436 KB |
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=101000; int n,_[N],a[N],id[10000005],f[N]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } struct edge{ int u,v,w; bool operator<(const edge oth) const{return w<oth.w;} }; vector<edge> ed; bool x[10000005]; int main() { scanf("%d",&n); rep(i,0,n) f[i]=i; rep(i,0,n) scanf("%d",&_[i]),x[_[i]]=true; sort(_,_+n); int nxt=0; rep(i,0,n) if (i==0||_[i]!=_[i-1]) a[nxt++]=_[i]; n=nxt; int pos=n-1; per(i,1,10000000) { if (x[i]) id[i]=pos,pos--; else id[i]=id[i+1]; } rep(i,0,n) { assert(a[i]!=0); for (int j=a[i];j<=a[n-1];j+=a[i]) { int x=id[j+(j==a[i])]; ed.pb({i,x,a[x]%a[i]}); } } sort(all(ed)); ll ans=0; for (auto e:ed) { int x=find(e.u); int y=find(e.v); if (x!=y) { ans+=e.w; f[x]=y; } } printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 42692 KB | Output is correct |
2 | Correct | 217 ms | 90616 KB | Output is correct |
3 | Correct | 41 ms | 43216 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 39616 KB | Output is correct |
2 | Runtime error | 1632 ms | 786436 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 42948 KB | Output is correct |
2 | Correct | 41 ms | 40584 KB | Output is correct |
3 | Correct | 43 ms | 42948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 143 ms | 66372 KB | Output is correct |
2 | Correct | 358 ms | 91512 KB | Output is correct |
3 | Correct | 195 ms | 91500 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 43704 KB | Output is correct |
2 | Correct | 290 ms | 91076 KB | Output is correct |
3 | Correct | 132 ms | 66392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 235 ms | 90952 KB | Output is correct |
2 | Correct | 467 ms | 140836 KB | Output is correct |
3 | Correct | 178 ms | 66988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 46320 KB | Output is correct |
2 | Correct | 482 ms | 140732 KB | Output is correct |
3 | Correct | 180 ms | 66992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 191 ms | 75132 KB | Output is correct |
2 | Runtime error | 1026 ms | 786436 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 212 ms | 75336 KB | Output is correct |
2 | Runtime error | 970 ms | 786436 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 52648 KB | Output is correct |
2 | Runtime error | 1154 ms | 786436 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |