Submission #887237

#	Time	Username	Problem	Language	Result	Execution time	Memory
887237		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	113 ms	24180 KiB

cities

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("txt.in", "r", stdin);freopen("txt.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; return 0;}
#define int             long long

const int maxn = 1e5 + 5, LG = 21, MOD = 1e9+7;// 998244353
const ll inf =  1061109567;

int n, k, m, p[maxn], sz[maxn], ans;
vector<pair<int, pii>> edges;
vector<pii> g[maxn], mst[maxn];
vector<int> cities;
bitset<maxn> mark, c, exist;

int root(int v) {
    if(p[v] == v) return v;
    return p[v] = root(p[v]);
}

inline void mrg(int v, int u) {
    v = root(v), u = root(u);
    if(v == u) return;
    if(sz[u] > sz[v]) swap(v, u);
    sz[v] += sz[u];
    p[u] = v;
}

void DFS(int v, int parent){
    mark[v] = 1;
    for(auto u : mst[v]) {
        if(parent ^ u.F && !mark[u.F]) {
            ans += u.S;
            DFS(u.F, v);
        }
    }
}


void dfs(int v, int parent = -1) {
    //cerr << "currently is vertex : " << v << ' ' << parent << '\n';
    for(auto u : mst[v]) {
        if(u.F ^ parent) {
            dfs(u.F, v);
            if(exist[u.F]) {
                ans += u.S;
                DFS(u.F, v);
                exist[v] = 1;
            }
        }
    }
    if(c[v] && parent != -1) {
        exist[v] = 1;
      //  cerr << "EXIST \n";
    }
}

inline void prep_and_input() {
    cin >> n >> k >> m;
    for(int i = 0; i < k; ++i) {
        int x;
        cin >> x;
        cities.pb(x);
        c[x] = 1;
    }
    for(int i = 1; i <= n; ++i) sz[i] = 1, p[i] = i;
    for(int i = 0; i < m; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        g[v].pb({u, w});
        g[u].pb({v, w});
        edges.pb({w,{v, u}});
    }
}

inline void MST() {
    sort(all(edges));    
    for(int i = 0; i < len(edges); ++i) {
        int v = edges[i].S.F; int u = edges[i].S.S; int w = edges[i].F;
        if(root(v) == root(u)) continue;
        else {
            mrg(v, u);
            mst[v].pb({u,w});
            mst[u].pb({v, w});
        }
    }
}

inline void solve(){
    int v = cities.back();
    dfs(v);
    cout << ans;
}

signed main() { 
    ios::sync_with_stdio(0), cin.tie(0);
    prep_and_input();
    MST();
    solve();
}

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