oj.uz

Submission #1106937

# Submission time Handle Problem Language Result Execution time Memory
1106937 2024-10-31T09:27:23 Z hoangnoobpro Sirni (COCI17_sirni) C++17
84 / 140
 692 ms 635468 KB 
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define nmax 10000007
#define fi first
#define se second
#define ll int
ll t=1,n,m=0,i=0,j=0,d=0,x=0,k=0,y=0,z,a[nmax],f[nmax],h[nmax],cnt=0,pa[nmax],sz[nmax];
long long kq=0;
struct hm
{
    ll a,b,c;
}v[nmax];
bool cmp(hm a,hm b)
{
    return a.c<b.c;
}
ll findset(ll u)
{
    if(pa[u]==u)return u;
    return pa[u]=findset(pa[u]);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>a[i];
        x=max(x,a[i]);
        if(f[a[i]])
        {
            i--;
            n--;
            continue;
        }
        sz[i]=1;
        pa[i]=i;
        f[a[i]]=a[i];
    }
    sort(a+1,a+n+1);
    for(i=x;i>=1;--i)
    {
        if(!f[i])f[i]=f[i+1];
    }
    d=0;
    f[0]=f[1]-1;
    for(i=1;i<=x;++i)
    {
        if(f[i]!=f[i-1])d++;
        h[i]=d;
    }
    for(i=1;i<=n;++i)
    {
        for(j=a[i];j<=x;j+=a[i])
        {
            y=j;
            if(j==a[i])y++;
            if(y>x)break;
//            if(f[y]<j+a[i])
            {
                v[++cnt].a=i;
                v[cnt].b=h[y];
                v[cnt].c=f[y]%a[i];
            }
        }
    }
    sort(v+1,v+cnt+1,cmp);
    kq=0;
    for(i=1;i<=cnt;++i)
    {
        x=findset(v[i].a);
        y=findset(v[i].b);
        if(x!=y)
        {
            if(sz[x]<sz[y])swap(x,y);
            sz[x]+=sz[y];
            pa[y]=x;
            kq+=v[i].c;
        }
    }
    cout<<kq;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 84572 KB Output is correct
2 Correct 235 ms 117324 KB Output is correct
3 Correct 54 ms 86644 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Runtime error 540 ms 635468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 84464 KB Output is correct
2 Correct 45 ms 84496 KB Output is correct
3 Correct 53 ms 84552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 29008 KB Output is correct
2 Correct 311 ms 65864 KB Output is correct
3 Correct 153 ms 43332 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18768 KB Output is correct
2 Correct 186 ms 43532 KB Output is correct
3 Correct 78 ms 27036 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 45588 KB Output is correct
2 Correct 379 ms 86572 KB Output is correct
3 Correct 137 ms 39248 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15796 KB Output is correct
2 Correct 417 ms 88688 KB Output is correct
3 Correct 132 ms 41296 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 100936 KB Output is correct
2 Runtime error 630 ms 635272 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 107264 KB Output is correct
2 Runtime error 645 ms 635464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 86600 KB Output is correct
2 Runtime error 692 ms 635216 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -