Submission #725461

#	Time	Username	Problem	Language	Result	Execution time	Memory
725461		vjudge1	Kronican (COCI16_kronican)	C++17	70 / 100	1 ms	212 KiB

kronican

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

const int MN=21;

int n,k;
int board[MN][MN];
int par[MN];
bool check[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;
    build();
    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;
        if(check[l]) continue;
        check[l]=true;
        check[r]=false;
        
        unionn(l,r);
        ans+=temp.weight;
        --cnt;
    }

    cout<<ans;
}

• Subtask 1: 70 / 100