# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
171910 | 2019-12-30T15:29:02 Z | rzbt | Sirni (COCI17_sirni) | C++14 | 4006 ms | 537268 KB |
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 100005 #define MAXB 10000007 typedef long long ll; using namespace std; int n; int niz[MAXN]; vector< pair<int,int> > s; vector<pair<int,int> > grane[MAXB]; int cale[MAXN],vel[MAXN]; int koren(int p){ while(p!=cale[p]){ cale[p]=cale[cale[p]]; p=cale[p]; } return p; } ll res=0; void spoji(int a,int b,int c){ a=koren(a); b=koren(b); if(a==b)return; res+=c; if(vel[a]<vel[b])swap(a,b); cale[b]=a; vel[a]+=vel[b]; } int main() { for(int i=0;i<MAXN;i++){ cale[i]=i; vel[i]=1; } scanf("%d", &n); for(int i=1;i<=n;i++){ scanf("%d",niz+i); } sort(niz+1,niz+n+1); for(int i=1;i<=n;i++) if(niz[i]!=niz[i+1]) s.pb(mp(niz[i],i)); for(int i=1;i<=n;i++){ if(niz[i]==niz[i+1]){ grane[0].pb(mp(i,i+1)); continue; } for(int j=niz[i];j<MAXB;j+=niz[i]){ auto a=lower_bound(all(s),mp(j+(j==niz[i]?1:0),0)); if(a==s.end())break; while(j+niz[i]<=a->F)j+=niz[i]; grane[a->F-j].pb(mp(i,a->second)); } } for(int i=0;i<MAXB;i++){ for(auto x:grane[i]){ spoji(x.F,x.S,i); } } printf("%lld",res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 251 ms | 236156 KB | Output is correct |
2 | Correct | 270 ms | 238328 KB | Output is correct |
3 | Correct | 249 ms | 236280 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 248 ms | 236092 KB | Output is correct |
2 | Correct | 274 ms | 236776 KB | Output is correct |
3 | Correct | 247 ms | 236152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 256 ms | 236052 KB | Output is correct |
2 | Correct | 247 ms | 236148 KB | Output is correct |
3 | Correct | 285 ms | 236316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 428 ms | 248560 KB | Output is correct |
2 | Correct | 781 ms | 274348 KB | Output is correct |
3 | Correct | 484 ms | 252776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 265 ms | 237688 KB | Output is correct |
2 | Correct | 497 ms | 259704 KB | Output is correct |
3 | Correct | 402 ms | 248936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 590 ms | 259756 KB | Output is correct |
2 | Correct | 961 ms | 288832 KB | Output is correct |
3 | Correct | 489 ms | 250976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 309 ms | 240300 KB | Output is correct |
2 | Correct | 788 ms | 283404 KB | Output is correct |
3 | Correct | 442 ms | 250704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 426 ms | 250200 KB | Output is correct |
2 | Correct | 2605 ms | 445640 KB | Output is correct |
3 | Correct | 459 ms | 252464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 429 ms | 250344 KB | Output is correct |
2 | Correct | 3939 ms | 537268 KB | Output is correct |
3 | Correct | 553 ms | 256392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 280 ms | 238496 KB | Output is correct |
2 | Correct | 4006 ms | 532488 KB | Output is correct |
3 | Correct | 451 ms | 252388 KB | Output is correct |