#include <bits/stdc++.h>
using namespace std;
struct edge {
int u, v, w;
};
struct DSU {
vector<int> parent;
void init(int n) {
parent.clear();
parent.resize(n + 1);
for (int i = 0; i <= n; i++)
parent[i] = i;
}
int findParent(int v) {
if (parent[v] != v)
parent[v] = findParent(parent[v]);
return parent[v];
}
void connect(int u, int v) {
u = findParent(u);
v = findParent(v);
if (u == v)
return;
parent[v] = u;
}
bool connected(int u, int v) {
u = findParent(u);
v = findParent(v);
return (u == v);
}
};
const int MAX_N = 500;
const int MAX_M = 1e5;
const int MAX_Q = 1e6;
vector<int> importantEdgesLower[MAX_M + 1], importantEdgesGreater[MAX_M + 2];
edge edges[MAX_M + 1];
DSU dsu;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int e = 1; e <= m; e++)
cin >> edges[e].u >> edges[e].v >> edges[e].w;
sort(edges + 1, edges + 1 + m, [](edge a, edge b) {
return a.w < b.w;
});
for (int e = 1; e <= m; e++) {
dsu.init(n);
dsu.connect(edges[e].u, edges[e].v);
importantEdgesLower[e].push_back(e);
for (int f: importantEdgesLower[e - 1]) {
if (!dsu.connected(edges[f].u, edges[f].v)) {
dsu.connect(edges[f].u, edges[f].v);
importantEdgesLower[e].push_back(f);
}
}
}
for (int e = m; e >= 1; e--) {
dsu.init(n);
dsu.connect(edges[e].u, edges[e].v);
importantEdgesGreater[e].push_back(e);
for (int f: importantEdgesGreater[e + 1]) {
if (!dsu.connected(edges[f].u, edges[f].v)) {
dsu.connect(edges[f].u, edges[f].v);
importantEdgesGreater[e].push_back(f);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int w;
cin >> w;
int l = 0, r = m + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (edges[mid].w > w)
r = mid;
else
l = mid;
}
dsu.init(n);
int j = 0;
long long cost = 0;
for (int e: importantEdgesLower[l]) {
while (j < (int)importantEdgesGreater[r].size() && edges[importantEdgesGreater[r][j]].w - w < w - edges[e].w) {
int f = importantEdgesGreater[r][j];
if (!dsu.connected(edges[f].u, edges[f].v)) {
dsu.connect(edges[f].u, edges[f].v);
cost += edges[f].w - w;
}
j++;
}
if (!dsu.connected(edges[e].u, edges[e].v)) {
dsu.connect(edges[e].u, edges[e].v);
cost += w - edges[e].w;
}
}
while (j < (int)importantEdgesGreater[r].size()) {
int f = importantEdgesGreater[r][j];
if (!dsu.connected(edges[f].u, edges[f].v)) {
dsu.connect(edges[f].u, edges[f].v);
cost += edges[f].w - w;
}
j++;
}
cout << cost << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |