Submission #1309970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309970		quollcucumber`	Netrpeljivost (COI23_netrpeljivost)	C++20	0 / 100	1 ms	332 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int parent[2048];
int dsu(int node) {
    if(parent[node] == node) return node;
    return parent[node] = dsu(parent[node]);
}
signed main(){
    for(int i = 0; i < 2048; i++) parent[i]= i;
    int n;
    cin >> n;
    int anti[n][n];
    vector<pair<int, pair<int, int>>> edges;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> anti[i][j];
            edges.push_back({anti[i][j], {i, j}});
        }
    }
    sort(edges.begin(), edges.end());
    int total = 0;
    int numedges[n];
    for(int i = 0; i < n ; i++) numedges[i] = 0;
    for(int i = 0; i < n * n; i++) {
        if(numedges[edges[i].second.first] < 2 && numedges[edges[i].second.second] < 2 && dsu(edges[i].second.first) != dsu(edges[i].second.second)) {
            total += edges[i].first;
            parent[dsu(edges[i].second.first)] = dsu(edges[i].second.second);
            numedges[edges[i].second.first]++;
            numedges[edges[i].second.second]++;
        }
    }
    cout<<total<<'\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 17
• Subtask 3: 0 / 32
• Subtask 4: 0 / 41