Submission #1170850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170850		fmalko	Cities (BOI16_cities)	C++20	0 / 100	139 ms	3564 KiB

cities

#include <bits/stdc++.h>
using namespace std;
int n,k,m;
const int MAXN = 100001;
int parent[MAXN];
int r[MAXN];
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
int f(int i) 
{
        return (parent[i] == i) ? i : (parent[i] = f(parent[i]));
}
void u(int x, int y) 
{
        int s1 = f(x), s2 = f(y);
        if (s1 != s2) {
            if (r[s1] < r[s2]) parent[s1] = s2;
            else if (r[s1] > r[s2]) parent[s2] = s1;
            else parent[s2] = s1, r[s1]++;
        }
}
void prep(int x) 
{
        for (int i = 0; i < x; i++)
        {
            parent[i] = i;
            r[i] = 1;
        }
}

int kruskal()
{
    int cost=0,count = 0;
    while(!pq.empty())
    {
        auto [w,x,y] = pq.top();
        pq.pop();
        if (f(x) != f(y)) {
            u(x, y);
            cost += w;
            if (++count == n - 1) break;
        }
    }
    return cost;
}
int main()
{
    cin >> n >> k >> m;
    for(int i = 0 ; i < k ; i++)
    {
        int x;
        cin >> x;
    }
    for(int i = 0 ; i < m ; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        pq.push({z,x,y});
    }
    auto l = pq.top();
    //cout << "PQ TOP : " << get<1>(l) << " " << get<2>(l) << " " << get<0>(l) << endl;
    prep(n);
    cout << kruskal();
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26