Submission #85802

#	Time	Username	Problem	Language	Result	Execution time	Memory
85802		Vasiljko	Sirni (COCI17_sirni)	C++14	42 / 140	887 ms	9384 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 1e3+5;

int n,p[N],par[N];
vector<int>v[N];
ll ans;

struct Edge{
    int from,to;
    ll w;
    Edge(int _from=0,int _to=0,ll _w=0){
        from=_from;
        to=_to;
        w=_w;
    }

    bool operator < (const Edge &t) const{
        return w<t.w;
    }
};

vector<Edge>e;

int Find(int x){if(par[x]==x)return x;return Find(par[x]);}
void Unite(int x,int y){
    x=Find(x);
    y=Find(y);

    par[x]=y;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        par[i]=i;
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int cost=min(p[i]%p[j],p[j]%p[i]);
            e.push_back(Edge(i,j,cost));
        }
    }

    sort(e.begin(),e.end());

    for(auto t:e){
        int from=t.from;
        int to=t.to;
        ll w=t.w;

        if(Find(from)!=Find(to)){
            Unite(from,to);
            ans+=w;
        }
    }

    cout<<ans;
    return 0;
}

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