oj.uz

답안 #156065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156065 2019-10-03T06:54:55 Z ionanghelina Sirni (COCI17_sirni) C++14
98 / 140
 5000 ms 786436 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;
vector<pair<int,int> > e[maxV];

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 taken=0;

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];
        if(x>=v[n]) continue;

        int ind=upper_bound(v+1,v+n+1,x)-v;



        e[cost(i,nrm[ind])].push_back({i,nrm[ind]});
        int lst=nrm[ind];

        for(int j=x+x;j<=v[n];j+=x)
        {
            if(j>v[n]) continue;

            ind=lower_bound(v+1,v+n+1,j)-v;

            if(nrm[ind]!=lst) e[cost(i,nrm[ind])].push_back({i,nrm[ind]});
            lst=nrm[ind];
        }
    }



    for(int i=0;i<=v[n];i++)
        for(auto it:e[i])
    edges.push_back({it.first,it.second,i});

    //for(auto it:edges)
      //  printf("%d %d% d\n",it.x,it.y,it.cost);

    dsu D=dsu(n);


    for(auto it:edges)
    {
        if(taken==cnt-1) break;
        x=it.x;
        y=it.y;
        cst=it.cost;

        tx=D.getRoot(x);
        ty=D.getRoot(y);

        if(tx!=ty)
        {
            taken++;
            sol+=1LL*cst;
            D.unite(tx,ty);
        }
    }


    printf("%lld\n",sol);

    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
sirni.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&v[i]);
         ~~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 235512 KB Output is correct
2 Correct 365 ms 240816 KB Output is correct
3 Correct 248 ms 235768 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 235508 KB Output is correct
2 Correct 1112 ms 237056 KB Output is correct
3 Correct 289 ms 235868 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 235344 KB Output is correct
2 Correct 274 ms 235292 KB Output is correct
3 Correct 251 ms 235512 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 258404 KB Output is correct
2 Correct 942 ms 323288 KB Output is correct
3 Correct 524 ms 276296 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 240212 KB Output is correct
2 Correct 590 ms 307320 KB Output is correct
3 Correct 437 ms 259552 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 707 ms 307032 KB Output is correct
2 Correct 1188 ms 386960 KB Output is correct
3 Correct 509 ms 274864 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 245196 KB Output is correct
2 Correct 1083 ms 382912 KB Output is correct
3 Correct 502 ms 274576 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 509 ms 273008 KB Output is correct
2 Runtime error 4147 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 273552 KB Output is correct
2 Execution timed out 5109 ms 530372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 241008 KB Output is correct
2 Execution timed out 5108 ms 729544 KB Time limit exceeded
3 Halted 0 ms 0 KB -