Submission #111919

#	Time	Username	Problem	Language	Result	Execution time	Memory
111919		someone_aa	Cities (BOI16_cities)	C++17	0 / 100	352 ms	14804 KiB

cities

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
vector<pair<int,int> > g[maxn];
vector<pair<int, pair<int,int> > > edges;
ll n, m, k;

ll x[10];
bool important[maxn];
ll usize[maxn], uparent[maxn];
bool sbt[maxn];

ll result;

int uroot(int x) {
    while(x != uparent[x]) {
        x = uparent[x];
    }
    return x;
}

void unite(int x, int y) {
    x = uroot(x);
    y = uroot(y);

    if(usize[x] > usize[y]) {
        uparent[y] = x;
        usize[x] += usize[y];
    }
    else {
        uparent[x] = y;
        usize[y] += usize[x];
    }
}

void dfs(int node, int p) {
    if(important[node]) sbt[node] = true;

    for(pair<int,int> i:g[node]) {
        if(i.first != p) {
            dfs(i.first, node);
            sbt[node] |= sbt[i.first];
        }
    }


    for(auto i:g[node]) {
        if(i.first != p && sbt[i.first]) {
            result += 1LL * i.second;
        }
    }
}

int main() {
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++){
         cin>>x[i];
         important[x[i]] = true;
    }

    int a, b, c;
    for(int i=0;i<m;i++) {
        cin>>a>>b>>c;

        edges.pb(mp(c, mp(a, b)));
    }

    for(int i=1;i<=n;i++) {
        usize[i] = 1;
        uparent[i] = i;
    }

    sort(edges.begin(), edges.end());

    int total = 0;
    for(auto i:edges) {
        int cost = i.first;
        int a = i.second.first; int aa = uroot(a);
        int b = i.second.second; int bb = uroot(b);

        if(aa == bb) continue;
        unite(aa, bb);
        g[a].pb(mp(b, cost));
        g[b].pb(mp(a, cost));
        total += cost;
    }

    dfs(x[1], -1);
    cout<<result<<"\n";
    return 0;
}

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