Submission #1237604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237604		qrn	Cities (BOI16_cities)	C++20	0 / 100	79 ms	21160 KiB

cities

#include "bits/stdc++.h"
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long
// #define intt int

const intt mod = 1e9 + 7;
const intt mxN = 4e5 + 5;
const intt inf = 1e18 + 10;

struct DSU {
	vector<intt> parent, sze;
	DSU(intt N) {
		parent.resize(N + 1);
		sze.resize(N + 1);
		for(intt i = 1; i <= N; i++) {
			parent[i] = i;
			sze[i] = 1;
		}
	}

	intt root(intt x) {
		if(parent[x] == x) return x;
		else return parent[x] = root(parent[x]); 
	}

	void unite(intt a, intt b) {
		a = root(a);
		b = root(b);
		if(a == b) return;
		if(sze[a] < sze[b]) swap(a,b);
		parent[b] = a;
		sze[a] += sze[b];
	}

};

vector<vector<pair<intt,intt>>>  graph;
vector<intt> important(mxN), koko(mxN);
vector<array<intt,3>> edges;

bool cmp(array<intt,3> &a, array<intt,3> &b) {
	if(a[2] == b[2]) {
		if(a[1] == b[1]) return a[0] < b[0];
		return a[1] < b[1];
	}
	return a[2] < b[2];
}

vector<intt> path;
void dfs(intt node, intt parent) {
	path.pb(node);
	for(auto u : graph[node]) {
		if(u.fi != parent) {
			dfs(u.fi, node);	
		}
	}
	if(important[node]) {
		for(intt i : path) koko[i] = 1;
	}
	path.pop_back();
}

void solve() {
	intt N, M, K;
	cin >> N >> K >> M;
	graph.assign(N + 1, vector<pair<intt,intt>> {});
	
	DSU dsu(N + 51);
	intt root = 0;
	for(intt i = 0; i < K; i++) {
		intt x; cin >> x; important[x] = 1;
		if(i == 0) root = x;
	}
	for(intt i = 0; i < M; i++) {
		intt a, b, w;
		cin >> a >> b >> w;
		edges.pb({a, b, w});
	}
	sort(ALL(edges), cmp);

	intt cost = 0;
	for(intt i = 0; i < M; i++) {
		intt a = edges[i][0], b = edges[i][1], w = edges[i][2];
		if(dsu.root(a) != dsu.root(b)) {
			dsu.unite(a, b);
			// cout << a << " " << b << " " << w << endl;
			graph[a].pb({b, w});
			graph[b].pb({a, w});
			cost += w;
		}
	}
	// cout << cost << endl;
	dfs(root, root);

	vector<intt> silindi(N + 1, 0ll);
	for(intt i = 1; i <= N; i++){
		// cout << koko[i] << " ";
		if(!koko[i]) {
			for(auto u : graph[i]) {
				if(!silindi[u.fi]) {
					cost -= u.se;
				}
			}
			silindi[i] = 1;
		}
	}
	// cout << endl;
	cout << cost << endl;
}

signed main() {
	SPEED;
	intt tst = 1;
  	// cin >> tst;
    	while (tst--) {
        	solve();
    	}
}


/*
	p00000
*/

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