oj.uz

Submission #725052

# Submission time Handle Problem Language Result Execution time Memory
725052 2023-04-16T15:08:37 Z vjudge1 Kronican (COCI16_kronican) C++17
0 / 100
 43 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN=21;

int n,k;
int board[MN][MN];
int par[MN];

struct mst{
    int left;
    int right;
    int weight;
}temp;

bool operator < (mst x,mst y){
    return x.weight>y.weight;
}

void build(){
    for(int i=1;i<=n;++i){
        par[i]=-1;
    }
}

int find(int u){
    if(par[u]<0) return u;
    return par[u]=find(par[u]);
}

void unionn(int a,int b){
    a=find(a);
    b=find(b);

    if(a==b) return;
    par[a]+=par[b];
    par[b]=a;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    
    priority_queue<mst> pq;
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>board[i][j];
            if(i!=j){
                temp.left=i;
                temp.right=j;
                temp.weight=board[i][j];
                pq.push(temp);
            }
        }
    }

    int cnt=n-k,ans=0;

    while(cnt>0){
        temp=pq.top();
        pq.pop();

        int l=temp.left,r=temp.right;
        if(find(l)==find(r)) continue;

        unionn(l,r);
        ans+=temp.weight;
        --cnt;
    }

    cout<<ans;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 65536 KB Execution killed with signal 9
2 Runtime error 41 ms 65536 KB Execution killed with signal 9
3 Runtime error 41 ms 65536 KB Execution killed with signal 9
4 Runtime error 42 ms 65536 KB Execution killed with signal 9
5 Runtime error 41 ms 65536 KB Execution killed with signal 9
6 Runtime error 43 ms 65536 KB Execution killed with signal 9
7 Runtime error 40 ms 65536 KB Execution killed with signal 9
8 Runtime error 41 ms 65536 KB Execution killed with signal 9
9 Runtime error 41 ms 65536 KB Execution killed with signal 9
10 Runtime error 40 ms 65536 KB Execution killed with signal 9