Submission #1111075

#TimeUsernameProblemLanguageResultExecution timeMemory
1111075f0rizenCities (BOI16_cities)C++17
0 / 100
854 ms22676 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9 + 7; const ll infll = 1e18; template<typename T> istream &operator>>(istream &is, vector<T> &a) { for (auto &i : a) { is >> i; } return is; } struct Edge { int u, v, w; bool operator<(const Edge &p) { return w < p.w; } }; struct DSU { vector<int> p, sz; DSU() {} DSU(int n) { p.resize(n); iota(p.begin(), p.end(), 0); sz.resize(n, 1); } int root(int v) { if (p[v] == v) { return v; } return p[v] = root(p[v]); } bool same(int u, int v) { return root(u) == root(v); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) { return false; } if (sz[u] > sz[v]) { swap(u, v); } p[u] = v; sz[v] += sz[u]; return true; } }; struct BinaryJumps { static const int lg = 17; vector<int> d; vector<vector<int>> up; BinaryJumps() {} BinaryJumps(int n) { d.resize(n); up.resize(lg, vector<int>(n, -1)); } void add_leaf(int v, int p) { d[v] = d[p] + 1; up[0][v] = p; for (int i = 1; i < lg; ++i) { if (up[i - 1][v] != -1) { up[i][v] = up[i - 1][up[i - 1][v]]; } } } int la(int v, int k) { for (int i = lg - 1; i >= 0; --i) { if (k >= (1 << i)) { k -= (1 << i); v = up[i][v]; } } return v; } int lca(int u, int v) { if (d[u] < d[v]) { swap(u, v); } u = la(u, d[u] - d[v]); for (int i = lg - 1; i >= 0; --i) { if (up[i][u] != up[i][v]) { u = up[i][u]; v = up[i][v]; } } if (u == v) { return u; } return up[0][u]; } int dist(int u, int v) { int w = lca(u, v); return d[u] + d[v] - 2 * d[w]; } bool on_path(int u, int v, int a) { return dist(u, a) + dist(a, v) == dist(u, v); } }; vector<vector<pair<int, int>>> g; BinaryJumps tr; void dfs(int v, int p = -1) { for (auto [u, w] : g[v]) { if (u != p) { tr.add_leaf(u, v); dfs(u, v); } } } int32_t main() { #ifdef LOCAL freopen("/tmp/input.txt", "r", stdin); #else ios::sync_with_stdio(false); cin.tie(nullptr); #endif int n, k, m; cin >> n >> k >> m; vector<int> a(k); cin >> a; for (auto &i : a) { --i; } vector<Edge> edg(m); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; edg[i] = {u, v, w}; } sort(edg.begin(), edg.end()); DSU dsu(n); g.resize(n); vector<Edge> mst; for (auto [u, v, w] : edg) { if (dsu.unite(u, v)) { g[u].push_back({v, w}); g[v].push_back({u, w}); mst.push_back({u, v, w}); } } tr = BinaryJumps(n); dfs(0); ll ans = 0; for (auto [u, v, w] : mst) { bool ok = false; for (auto i : a) { for (auto j : a) { if (tr.on_path(i, j, u) && tr.on_path(i, j, v)) { ok = true; } } } if (ok) { ans += w; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...