oj.uz

답안 #701013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701013 2023-02-19T17:48:05 Z amin Sirni (COCI17_sirni) C++14
112 / 140
 1106 ms 786432 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
ll nex[10000002];
ll sz[10000002],vis[10000002];
ll p[20000000];
ll ans=0;
int par(int x)
{
    if(p[x]==x)
    return x;
    p[x]=par(p[x]);
    return p[x];
}
void un(int x,int y,ll cost)
{
    //cout<<x<<' '<<y<<' '<<cost<<endl;
    x=par(x);
    y=par(y);
    if(x==y)
    {
        return ;
    }
    ans+=cost;
if(sz[x]<sz[y])
{
    swap(x,y);
}
sz[x]+=sz[y];
sz[y]=0;
p[y]=x;
}

int main()
{
    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        p[a[i]]=a[i];
        sz[a[i]]=1;
        nex[a[i]]=a[i];
    }
    for(int i=10000000;i>=0;i--)
    {
        if(nex[i]==i)
        {
            continue;
        }
        nex[i]=nex[i+1];
    }
   vector<pair<ll,ll> >v[10000000];
    for(int i=1;i<=1e7;i++)
    {
        if(nex[i]==i&&vis[i]==0)
        {
            vis[i]=1;
            for(int y=i;y<=1e7;y+=i)
            {
                vis[y]=1;
             //   if(nex[y]!=0)
             if(nex[y]==y)
             {
                 v[0].push_back({i,y});
             }
            if(nex[y+1]!=0)
                v[nex[y+1]%i].push_back({i,nex[y+1]});
            }
        }
    }
    for(ll i=0;i<1e7;i++)
    {
        for(auto y:v[i])
        {
            un(y.first,y.second,i);
        }
    }
    cout<<ans;

}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 339936 KB Output is correct
2 Correct 393 ms 453308 KB Output is correct
3 Correct 248 ms 377764 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 391988 KB Output is correct
2 Correct 815 ms 689808 KB Output is correct
3 Correct 253 ms 401252 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 341860 KB Output is correct
2 Correct 219 ms 327876 KB Output is correct
3 Correct 227 ms 354920 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 424336 KB Output is correct
2 Correct 578 ms 441480 KB Output is correct
3 Correct 556 ms 446976 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 411120 KB Output is correct
2 Correct 549 ms 426764 KB Output is correct
3 Correct 534 ms 415140 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 573 ms 434852 KB Output is correct
2 Correct 528 ms 452208 KB Output is correct
3 Correct 437 ms 432548 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 417 ms 400000 KB Output is correct
2 Correct 550 ms 445600 KB Output is correct
3 Correct 496 ms 443900 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 457 ms 572360 KB Output is correct
2 Runtime error 678 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 597 ms 582472 KB Output is correct
2 Runtime error 714 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 307 ms 497160 KB Output is correct
2 Correct 1106 ms 754808 KB Output is correct
3 Correct 548 ms 455204 KB Output is correct