Submission #89138

# Submission time Handle Problem Language Result Execution time Memory
89138 2018-12-10T13:54:58 Z asifthegreat Kronican (COCI16_kronican) C++14
10 / 100
3 ms 1000 KB
#include <bits/stdc++.h>
using namespace std;

const int N = 100000;

int parent[N];

struct MST{
    int x,y,val;
};
bool operator<(MST a , MST b){return a.val < b.val;}

vector<MST>v;

int Find(int n)
{
    if(n == parent[n])return n;
    return parent[n] = Find(parent[n]);
}
void Union(int a,int b)
{
    parent[Find(a)] = Find(b);
}

int main()
{
    for(int i = 0; i < N;i++)parent[i] = i;
    int n,k;
    scanf("%d%d",&n,&k);
    k = n-k;
    int val;
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <= n;j++){
            scanf("%d",&val);
            if(i == j)continue;
            else{
                v.push_back({i,j,val});
            }
        }
    }
    sort(v.begin(),v.end());
    int sum = 0;
    for(auto i: v){
        if(Find(i.x)==Find(i.y))continue;
        if(!k)break;
        sum += i.val;
        k--;
        Union(i.x,i.y);

    }
    printf("%d\n",sum);
    return 0;
}

Compilation message

kronican.cpp: In function 'int main()':
kronican.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
kronican.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&val);
             ~~~~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Incorrect 2 ms 888 KB Output isn't correct
3 Incorrect 2 ms 888 KB Output isn't correct
4 Incorrect 3 ms 888 KB Output isn't correct
5 Incorrect 3 ms 1000 KB Output isn't correct
6 Incorrect 2 ms 1000 KB Output isn't correct
7 Incorrect 2 ms 1000 KB Output isn't correct
8 Incorrect 1 ms 1000 KB Output isn't correct
9 Incorrect 2 ms 1000 KB Output isn't correct
10 Incorrect 3 ms 1000 KB Output isn't correct