#pragma GCC optimize ("O3", "unroll-loops")
#pragma GCC target ("avx2")
//#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define all_of(v) (v).begin(), (v).end()
#define fi first
#define se second
const int MAXM = 100005;
const int MAXN = 505;
const int SIZE = 400;
const LL INF = (LL) 1e9 + 8763;
using namespace std;
struct Edge {
int u, v;
LL w;
};
struct DSU {
// 1-based roll-back DSU
struct Record {
int x, y; // y is merged into x
};
int pa[MAXN], sz[MAXN];
vector<Record> stk;
void init(int n) {
stk.clear();
for (int i = 1; i <= n; i++) {
pa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
return x == pa[x] ? x : find(pa[x]);
}
int merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) {
stk.push_back((Record){-1, -1});
return 0;
}
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
pa[y] = x;
stk.push_back((Record){x, y});
return 1;
}
int same(int x, int y) {
return find(x) == find(y);
}
void roll_back() {
assert(!stk.empty());
Record r = stk.back();
stk.pop_back();
if (r.x != -1) {
pa[r.y] = r.y;
sz[r.x] -= sz[r.y];
}
}
};
int n, m, sq;
Edge E[MAXM];
int vis[MAXN];
PII parent[MAXN];
vector<PII> G[MAXN];
DSU D[MAXM / SIZE + 5];
int qn;
vector<int> X;
void compute(vector<int> &res) {
int cnt = 0, pseudo = MAXM / SIZE + 4;
D[pseudo].init(n);
for (int i = 0; i < m; i++) {
// stage 1
int j, pre = i, last = pseudo;
for (j = cnt - 1; j >= 0; j--) {
if (D[j].same(E[i].u, E[i].v)) {
break;
}
pre = j * SIZE;
last = j;
}
// stage 2
int op = 0;
while (pre > 0) {
op++;
D[last].merge(E[pre - 1].u, E[pre - 1].v);
if (D[last].same(E[i].u, E[i].v)) {
break;
}
pre--;
}
res[i] = i - pre;
for (int i = 0; i < op; i++) {
D[last].roll_back();
}
// add E[i];
if (i % SIZE == 0) {
D[cnt++].init(n);
}
for (int j = 0; j < cnt; j++) {
D[j].merge(E[i].u, E[i].v);
}
}
}
vector<Edge> trim(vector<Edge> es) {
for (int i = 1; i <= n; i++) {
vis[i] = 0;
G[i].clear();
parent[i] = PII(-1, -1);
}
for (Edge e : es) {
G[e.u].push_back(PII(e.v, e.w));
G[e.v].push_back(PII(e.u, e.w));
}
function<void(int)> dfs = [&] (int v) {
vis[v] = 1;
for (PII p : G[v]) {
if (!vis[p.fi]) {
dfs(p.fi);
parent[p.fi] = PII(v, p.se);
}
}
};
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
}
}
vector<Edge> res;
for (int i = 1; i <= n; i++) {
if (parent[i].fi != -1) {
res.push_back((Edge){i, parent[i].fi, parent[i].se});
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
sq = (int)(sqrt(m) + 0.5);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
E[i] = (Edge){u, v, w};
}
sort(E, E + m, [&] (Edge e1, Edge e2) {
return e1.w < e2.w;
});
cin >> qn;
X.resize(qn);
for (int i = 0; i < qn; i++) {
cin >> X[i];
}
// trim useless edges
int lp = 0, sz = 0;
vector<Edge> temp = vector<Edge>(E, E + m);
while (lp < m) {
int rp = lp + 1;
while (temp[rp].w == temp[lp].w) {
rp++;
}
vector<Edge> F = trim(vector<Edge>(temp.begin() + lp, temp.begin() + rp));
for (Edge e : F) {
E[sz++] = e;
}
lp = rp;
}
// cout << "Trim " << m - sz << '\n';
m = sz;
// compute
vector<int> L(m), R(m);
compute(L);
reverse(E, E + m);
compute(R);
reverse(E, E + m);
reverse(all_of(R));
// cout << "Edge:\n";
// for (int i = 0; i < m; i++) {
// cout << E[i].u << ' ' << E[i].v << " " << E[i].w << '\n';
// }
// cout << "\n\nLR:\n";
// for (int i = 0; i < m; i++) {
// cout << L[i] << ' ' << R[i] << '\n';
// }
// make answer
vector<PII> ev;
for (int i = 0; i < m; i++) {
int l = i - L[i] - 1, r = i + R[i] + 1, wl, wr;
if (l < 0) {
wl = -INF;
}
else {
wl = (E[i].w + E[l].w) / 2 + 1;
}
if (r >= m) {
wr = INF;
}
else {
wr = (E[i].w + E[r].w) / 2;
}
int pl = lower_bound(all_of(X), wl) - X.begin();
int pr = upper_bound(all_of(X), wr) - X.begin();
ev.push_back(PII(pl, ~i));
ev.push_back(PII(pr, i));
}
// sweep
int ptr = 0;
vector<int> all, active(m);
vector<LL> ans(qn, 0);
sort(all_of(ev));
for (int i = 0; i < qn; i++) {
while (ev[ptr].fi <= i) {
int id = ev[ptr].se;
if (ev[ptr].se < 0) {
// insert
id = ~id;
assert(active[id] == 0);
active[id] = 1;
all.push_back(id);
}
else {
assert(active[id] == 1);
active[id] = 0;
}
ptr++;
}
// calc
int j = 0;
while (j < all.size()) {
if (!active[all[j]]) {
swap(all[j], all.back());
all.pop_back();
continue;
}
ans[i] += abs(E[all[j]].w - X[i]);
j++;
}
assert(all.size() == n - 1);
}
for (int i = 0; i < qn; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from reconstruction.cpp:5:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:246:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | while (j < all.size()) {
| ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from reconstruction.cpp:5:
reconstruction.cpp:255:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
255 | assert(all.size() == n - 1);
| ~~~~~~~~~~~^~~~~~~~
