//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 505
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct edge{
int u, v, w;
edge(){u = v = w = 0;}
edge(int a, int b, int c){u = a, v = b, w = c;}
};
inline void del(vector<pii> &v, pii x) {
v.erase(find(v.begin(), v.end(), x));
}
inline void del(vector<int> &v, int x) {
v.erase(find(v.begin(), v.end(), x));
}
struct graph{
vector<int> ed; //first < second
vector<pii> adj[maxn];
pii best;
int bid, t;
void init(int n) {
ed.clear();
t = 0;
for (int i = 0;i <= n;i++) adj[i].clear();
}
bool getpath(int n, int par, int goal) {
if (n == goal) return 1;
for (auto [v, id]:adj[n]) {
if (v != par && getpath(v, n, goal)) {
if (id < bid) {
bid = id;
best = {n, v};
}
return 1;
}
}
return 0;
}
void upd(int u, int v) {
bid = inf;
t++;
if (u > v) swap(u, v);
if (getpath(u, 0, v)) {
if (best.ff > best.ss) swap(best.ff, best.ss);
del(adj[best.ff], make_pair(best.ss, bid));
del(adj[best.ss], make_pair(best.ff, bid));
del(ed, bid);
}
adj[u].push_back({v, t});
adj[v].push_back({u, t});
ed.push_back(t);
}
} g;
vector<int> tree[100005];
struct DSU{
int par[maxn], siz[maxn];
void init(int n) {
for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
}
int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
bool Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return 0;
if (siz[a] < siz[b]) par[a] = b;
else par[b] = a;
return 1;
}
} dsu;
vector<int> wei;
vector<edge> ed;
ll ans[1000005];
int n, m;
vector<int> L, R;
vector<int> se(int x) {
int st = (int)R.size() - 1;
int l = (int)L.size()-1;
dsu.init(n);
vector<int> ret;
for (;st >= 0;st--) {
int il = L[l], ir = R[st];
while (l >= 0 && x - wei[il] <= wei[ir] - x) {
if (dsu.Union(ed[il].u, ed[il].v)) ret.push_back(il);
l--;
if (l >= 0) il = L[l];
}
if (dsu.Union(ed[ir].u, ed[ir].v)) ret.push_back(ir);
}
while (l >= 0) {
int il = L[l];
if (dsu.Union(ed[il].u, ed[il].v)) ret.push_back(il);
l--;
}
sort(ret.begin(), ret.end());
return ret;
}
void solve(vector<pii> v) {
if (v.size() == 0) return;
if (v.size() == 1) {
vector<int> e = se(v[0].ff);
for (int i:e) ans[v[0].ss] += abs(wei[i] - v[0].ff);
return;
}
vector<int> e = se(v[0].ff);
if (e == se(v.back().ff)) {
for (pii p:v) {
for (int i:e) ans[p.ss] += abs(wei[i] - p.ff);
}
return;
}
vector<pii> lef(v.begin(), v.begin() + (v.size() / 2));
vector<pii> rig(v.begin() + (v.size()/2), v.end());
solve(lef);
solve(rig);
}
int main() {
io
cin >> n >> m;
for (int i = 0;i < m;i++) {
int u, v, w;
cin >> u >> v >> w;
wei.push_back(w);
ed.push_back(edge(u, v, w));
}
sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
sort(wei.begin(), wei.end());
int q;
cin >> q;
vector<int> que(q);
for (int i = 0;i < q;i++) {
cin >> que[i];
}
//for (int i = m - 1;i >= 0;i--) debug(ed[i].u, ed[i].v, ed[i].w);
g.init(n);
for (int i = m - 1;i >= 0;i--) {
g.upd(ed[i].u, ed[i].v);
tree[i] = g.ed;
}
g.init(n);
int ind = 0;
auto answer = [&] (int LIM, int id) {
vector<pii> qi;
while (ind < q && que[ind] < LIM) {
qi.push_back({que[ind], ind});
ind++;
}
L = g.ed, R = tree[id];
for (int &i:R) i = m - i;
for (int &i:L) i--;
solve(qi);
};
for (int i = 0;i < m;i++) {
answer(ed[i].w, i);
g.upd(ed[i].u, ed[i].v);
}
answer(inf, m);
for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5176 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5176 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
5204 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5176 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5176 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
5176 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
