oj.uz

Submission #483524

# Submission time Handle Problem Language Result Execution time Memory
483524 2021-10-30T08:14:58 Z oneloveforever Sirni (COCI17_sirni) C++14
140 / 140
 3715 ms 711676 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=1e7+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>id;
    set<int>s;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    n=s.size();
    vector<int>a(n+1);
    n=0;
    for(int node:s)
    {
        ++n;
        a[n]=node;
    }
    for(int i=1; i<=n; i++)
    {
        int vt=i+1;
        for(int j=a[i]; j<M; j+=a[i])
        {
            while(vt<=n && a[vt]<j)vt++;
            if(vt<=n) edge[a[vt]%a[i]].push_back({i,vt});
        }
    }
    DSU dsu(n);
    ll 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 235332 KB Output is correct
2 Correct 193 ms 264476 KB Output is correct
3 Correct 130 ms 235460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 235276 KB Output is correct
2 Correct 1084 ms 630048 KB Output is correct
3 Correct 132 ms 235936 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 235284 KB Output is correct
2 Correct 136 ms 235176 KB Output is correct
3 Correct 136 ms 235348 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3205 ms 250256 KB Output is correct
2 Correct 2878 ms 278380 KB Output is correct
3 Correct 2148 ms 260628 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 237876 KB Output is correct
2 Correct 268 ms 259012 KB Output is correct
3 Correct 2192 ms 250060 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3132 ms 261780 KB Output is correct
2 Correct 3101 ms 295668 KB Output is correct
3 Correct 3005 ms 259176 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 240428 KB Output is correct
2 Correct 2123 ms 295760 KB Output is correct
3 Correct 2445 ms 260380 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2349 ms 253820 KB Output is correct
2 Correct 3117 ms 598744 KB Output is correct
3 Correct 2294 ms 257312 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2291 ms 257984 KB Output is correct
2 Correct 3715 ms 711676 KB Output is correct
3 Correct 2275 ms 313700 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 238532 KB Output is correct
2 Correct 3159 ms 599460 KB Output is correct
3 Correct 2592 ms 262592 KB Output is correct