# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
156059 | 2019-10-03T06:08:18 Z | ionanghelina | Sirni (COCI17_sirni) | C++14 | 2 ms | 504 KB |
#include<bits/stdc++.h> using namespace std; const int maxN=(1e5)+5; const int maxV=(1e7)+5; const int inf=INT_MAX; struct tip { int x,y,cost; bool operator<(const tip& other) { return cost<other.cost; } }; class dsu { private: int t[maxN]; public: dsu(int n) { for(int i=1;i<=n;i++) t[i]=-1; } inline int getRoot(int x) { //getting the root int y=x; while(t[y]>0) y=t[y]; //road compression int z=y; y=x; while(y!=z) { int aux=t[y]; t[y]=z; y=aux; } return y; } inline void unite(int x,int y) { int tx=getRoot(x); int ty=getRoot(y); if(tx<ty) { t[tx]+=t[ty]; t[ty]=tx; } else { t[ty]+=t[tx]; t[tx]=ty; } } }; vector<tip> edges; int n,v[maxN],cnt,M[maxV],nrm[maxN],x,y,cst,tx,ty; long long sol; inline int cost(int x,int y) { int xa,ya; xa=M[x]; ya=M[y]; return min((xa%ya),(ya%xa)); } int main() { freopen("sirni.in","r",stdin); freopen("sirni.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); sort(v+1,v+n+1); v[n+1]=inf; for(int i=1;i<=n;i++) { if(i==1 || v[i]!=v[i-1]) cnt++; M[cnt]=v[i]; nrm[i]=cnt; } for(int i=1;i<=cnt;i++) { int x=M[i]; int ind=upper_bound(v+1,v+n+1,x)-v; if(ind>n) continue; edges.push_back({i,nrm[ind],cost(i,nrm[ind])}); int lst=nrm[ind]; for(int j=x+x;j<=v[n];j+=x) { ind=lower_bound(v+1,v+n+1,j)-v; if(ind>n) break; if(nrm[ind]!=lst) edges.push_back({i,nrm[ind],cost(i,nrm[ind])}); lst=nrm[ind]; } } sort(edges.begin(),edges.end()); //for(auto it:edges) // printf("%d %d% d\n",it.x,it.y,it.cost); dsu D=dsu(n); for(auto it:edges) { x=it.x; y=it.y; cst=it.cost; tx=D.getRoot(x); ty=D.getRoot(y); if(tx!=ty) { sol+=1LL*cst; D.unite(tx,ty); } } printf("%lld\n",sol); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |