oj.uz

Submission #483517

# Submission time Handle Problem Language Result Execution time Memory
483517 2021-10-30T07:41:42 Z oneloveforever Sirni (COCI17_sirni) C++14
0 / 140
 73 ms 7344 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
int n;
const int M=1e5+7;
struct DSU
{
    vector<int>sz,trace;
    int n;
    DSU(int _n=0)
    {
        n=_n;
        sz.assign(n+7,1);
        trace.resize(n+7);
        iota(trace.begin(),trace.end(),0);
    }
    int find_dsu(int x)
    {
        return trace[x]==x?trace[x]:find_dsu(trace[x]);
    }
    bool check(int x,int y)
    {
        int u=find_dsu(x);
        int v=find_dsu(y);
        if(u==v)return false;
        if(sz[u]>sz[v])swap(u,v);
        trace[u]=v;
        sz[v]+=sz[u];
        return true;
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    vector<vector<ii> >edge(M+10);
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    for(int i=1;i<=n;i++)
    {
        int vt=i;
        for(int need=a[i];need<M;need+=a[i])
        {
            while(vt+1<=n&&a[vt+1]<=need)vt+=1;
            edge[a[vt]%a[i]].push_back(make_pair(i,vt));
            //cout<<vt<<" "<<i<<" "<<a[vt]<<" "<<a[i]<<" "<<need<<endl;
            if(vt==n)break;
        }
    }
    DSU dsu(n);
    int ans=0;
    for(int i=0;i<M;i++)
    {
        for(ii node:edge[i])
        {
            //cout<<node.x<<" "<<node.y<<" "<<i<<endl;
            if(dsu.check(node.x,node.y))ans+=i;
        }
    }
    cout<<ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 5528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 7344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3040 KB Output isn't correct
2 Halted 0 ms 0 KB -