Submission #84671

#	Time	Username	Problem	Language	Result	Execution time	Memory
84671		wjoao	Kronican (COCI16_kronican)	C++11	10 / 100	2 ms	720 KiB

kronican

#include<bits/stdc++.h>
#define maxn 25
#define maxn2 ((1<<21)+5)
#define inf 0x3f3f3f3f
#define pii pair<int, pair<int, int> >

using namespace std;

int n, k;
priority_queue< pii, vector< pii >, greater< pii > > fp;

struct UnionFind{
    int pai[maxn];

    UnionFind(){
        memset(pai, -1, sizeof pai);
    }

    int find(int i){
        if(pai[i] == -1) return i;
        pai[i] = find(pai[i]);
        return pai[i];
    }

    bool uni(int x, int y){
        if(find(x) == find(y)) return false;
        pai[find(y)] = find(x);
        return true;
    }

} uf;

int main(){
  scanf(" %d %d", &n, &k);
  k = n-k;
  for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++ ){
    int a;
    scanf("%d", &a);
    if( i != j )
    fp.push(make_pair(a, make_pair(i, j)));
  }
  int sol = 0;
  while(k--){
    int val = fp.top().first;
    int v = fp.top().second.first;
    int u = fp.top().second.second;
    fp.pop();

    if(uf.find(v) == uf.find(u)){
      k++;
      continue;
    }
    uf.uni(u, v);
    sol += val;
  }
  printf("%d\n", sol);
  return 0;
}

Compilation message (stderr)

kronican.cpp: In function 'int main()':
kronican.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~
kronican.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a);
     ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 100