oj.uz

Submission #85802

# Submission time Handle Problem Language Result Execution time Memory
85802 2018-11-21T14:51:21 Z Vasiljko Sirni (COCI17_sirni) C++14
42 / 140
 887 ms 9384 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 8928 KB Output is correct
2 Correct 469 ms 9152 KB Output is correct
3 Correct 830 ms 9152 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 9152 KB Output is correct
2 Correct 685 ms 9284 KB Output is correct
3 Correct 887 ms 9344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 9376 KB Output is correct
2 Correct 267 ms 9376 KB Output is correct
3 Correct 635 ms 9384 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 9384 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -