#include <bits/stdc++.h>
using namespace std;
//#define int long long
using ii = pair<int, int>;
using tp = tuple<int, int, int>;
const int N = 1e6 + 5;
const long long INF = 1e9;
int n, m, q, que[N];
vector<ii> ad[N];
struct DSU{
int pa[N], sz[N];
void mset(int n){
for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
}
int fset(int i){
return i == pa[i] ? i : pa[i] = fset(pa[i]);
}
bool uset(int u, int v){
u = fset(u), v = fset(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
pa[v] = u;
sz[u] += sz[v];
return true;
}
};
namespace sub12{
DSU d;
vector<tp> edge;
void solve(){
for(int u = 1; u <= n; u++)
for(auto [v, w] : ad[u]) edge.emplace_back(u, v, w);
for(int t = 1; t <= q; t++){
sort(edge.begin(), edge.end(), [&](tp x, tp y){
int a = get<2>(x), b = get<2>(y);
return abs(a - que[t]) < abs(b - que[t]);
});
d.mset(n);
long long res = 0;
for(auto [u, v, w] : edge)
if(d.uset(u, v)) res += 1LL*abs(w - que[t]);
cout << res << "\n";
}
}
}
namespace sub3{
vector<int> weight[N];
int ptr[N];
long long res[N];
vector<ii> query;
void solve(){
for(int i = 1; i < n; i++){
for(auto [j, w] : ad[i]) if(j == i + 1) weight[i].push_back(w);
sort(weight[i].begin(), weight[i].end());
}
for(int i = 1; i <= q; i++) query.emplace_back(que[i], i);
sort(query.begin(), query.end());
for(auto [x, id] : query){
for(int i = 1; i < n; i++){
while(ptr[i] + 1 < weight[i].size() && weight[i][ptr[i] + 1] <= x) ptr[i]++;
int tmp = abs(x - weight[i][ptr[i]]);
if(x >= weight[i][ptr[i]] && ptr[i] + 1 < weight[i].size()) tmp = min(tmp, abs(x - weight[i][ptr[i] + 1]));
res[id] += tmp;
}
}
for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v, w; cin >> u >> v >> w;
ad[u].emplace_back(v, w);
ad[v].emplace_back(u, w);
}
cin >> q;
for(int i = 1; i <= q; i++) cin >> que[i];
if(q <= 10) sub12::solve();
else sub3::solve();
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... |