oj.uz

Submission #111919

# Submission time Handle Problem Language Result Execution time Memory
111919 2019-05-16T19:43:54 Z someone_aa Cities (BOI16_cities) C++17
0 / 100
 352 ms 14804 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Incorrect 3 ms 2560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 14620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 14696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 14804 KB Output isn't correct
2 Halted 0 ms 0 KB -