Submission #1337170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337170		boyliguanhan	Sirni (COCI17_sirni)	C++17	112 / 140	5114 ms	447332 KiB

sirni

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int id[10001000];
int par[100100];
int abp(int x){
    return par[x]?par[x]=abp(par[x]):x;
}
int merge(int u,int v){
    u=abp(u);
    v=abp(v);
    return u==v?0:par[u]=v;
}
vector<pair<int,int>> edges[5000100];
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x,CC=0;
    cin>>n;
    set<int>st;
    while(n--)cin>>x,st.insert(x);
    for(auto i:st)id[i]=++CC;
    for(auto i:st) {
        int I=id[i];
        auto x = ++st.find(i);
        while(x!=st.end()) {
            edges[*x%i].push_back({id[*x],I});
            int z = *x/i;
            x++;
            if(x==st.end())break;
            if(*x <(z+1)*i)
                x=st.lower_bound((z+1)*i);
        }
    }
    long long cost=0;
    for(int i=0;i<5e6;i++)
        for(auto[u,v]:edges[i])
            if(merge(u,v))
                cost+=i;
    cout<<cost;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 14 / 14