Submission #447320

#	Time	Username	Problem	Language	Result	Execution time	Memory
447320		2548631	Kronican (COCI16_kronican)	C++17	10 / 100	1 ms	204 KiB

kronican

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

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i, l, r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (64 - __builtin_clzll(1ll * (x)) - 1)
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define Pi acos(-1.0l)
#define sz(x) int(x.size())
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ins insert
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';

typedef unsigned long long int ulli;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef vector<pli> vpli;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N=27;

int n, k;
int c[N][N];
vi pos;

int p[N], r[N];

void init(){
    forw(i,0,n){
        p[i]=i;
        r[i]=0;
    }
}

int root(int x){
    if(x==p[x])
        return x;
    return p[x]=root(p[x]);
}

bool unite(int x, int y){
    x=root(x);
    y=root(y);
    if(x==y)
        return false;
    if(r[x]>r[y])
        swap(x,y);
    p[x]=y;
    if(r[x]==r[y])
        r[y]++;
    return true;
}

void solve(){
    init();
    sort(all(pos),[&](int x, int y)
         {return c[x/n][x%n]<c[y/n][y%n];});
    int cnt=n, res=0;
    for(int i:pos){
        if(cnt==k)
            break;
        if(unite(i/n,i%n)){
            res+=c[i/n][i%n];
            cnt--;
        }
    }
    cout<<res;
}

void read(){
    cin>>n>>k;
    forw(i,0,n) forw(j,0,n){
        cin>>c[i][j];
        if(i!=j)
            pos.pb(n*i+j);
    }
}

int main(){
    fastIO;
#ifndef ONLINE_JUDGE
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
#endif
    read();
    solve();
    return 0;
}

• Subtask 1: 10 / 100