//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 maxm 100005
#define maxq 1000005
#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, id;
edge(){u = v = w = id = 0;}
edge(int a, int b, int c, int d){u = a, v = b, w = c, id = d;}
};
struct DSU{
int par[maxn], siz[maxn];
vector<pii> op;
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 : (find(par[a]));
}
bool Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) {
op.push_back({0, 0});
return 0;
}
if (siz[a] < siz[b]) swap(a, b);
siz[a] += siz[b];
par[b] = a;
op.push_back({a, b});
return 1;
}
void undo(int x) {
while (x--) {
assert(op.size() > 0);
int a = op.back().ff, b = op.back().ss;
if (a) {
siz[a] -= siz[b];
par[b] = b;
}
op.pop_back();
}
}
} dsu;
vector<int> wei;
pii ran[maxm];
void solve(int l, int r, vector<edge> ed, vector<edge> lef, vector<edge> rig) {
int m = (l + r) / 2;
vector<edge> el, er, l0, r0, e1, l1, r1;
int tot = ed.size() + lef.size() + rig.size();
if (tot == 0) return;
/*
debug(l, r);
for (auto e:ed) debug(e.id);
debug();
for (auto e:lef) debug(e.id);
debug();
for (auto e:rig) debug(e.id);
debug("pick");
*/
auto cmp = [&] (edge &x, edge &y){
return abs(x.w - m) < abs(y.w - m);
};
sort(ed.begin(), ed.end(), cmp);
sort(lef.begin(), lef.end(), cmp);
sort(rig.begin(), rig.end(), cmp);
int s0 = ed.size(), s1 = lef.size(), s2 = rig.size();
int i0 = 0, i1 = 0, i2 = 0;
for (int tmp = 0;tmp < tot;tmp++) {
int mi = (i0 < s0 ? 0 : (i1 < s1 ? 1 : 2));
edge cur = i0 < s0 ? ed[i0] : (i1 < s1 ? lef[i1] : rig[i2]);
if (i1 < s1 && cmp(lef[i1], cur)) {
cur = lef[i1], mi = 1;
}
if (i2 < s2 && cmp(rig[i2], cur)) {
cur = rig[i2], mi = 2;
}
if (mi == 0) {
i0++;
if (dsu.Union(cur.u, cur.v)) e1.push_back(cur);
else if (cur.w < m) el.push_back(cur);
else er.push_back(cur);
} else if (mi == 1) {
i1++;
if (dsu.Union(cur.u, cur.v)) l1.push_back(cur);
else l0.push_back(cur);
} else {
i2++;
if (dsu.Union(cur.u, cur.v)) r1.push_back(cur);
else r0.push_back(cur);
}
}
dsu.undo(tot);
for (auto e:e1) ran[e.id] = {m, m+1};
for (auto e:l1) ran[e.id].ff = m;
for (auto e:l0) ran[e.id].ff = r;
for (auto e:r1) ran[e.id].ss = m+1;
for (auto e:r0) ran[e.id].ss = l;
if (r - l == 1) return;
vector<edge> tr = r1, tl = l1;
tr.insert(tr.end(), e1.begin(), e1.end());
tl.insert(tl.end(), e1.begin(), e1.end());
int cnt = l1.size();
for (auto e:l1) dsu.Union(e.u, e.v);
solve(m+1, r, er, l0, tr);
dsu.undo(cnt);
cnt = r1.size();
for (auto e:r1) dsu.Union(e.u, e.v);
solve(l, m+1, el, tl, r0);
dsu.undo(cnt);
}
bool on[maxm];
int main() {
io
int n, m;
cin >> n >> m;
vector<edge> ed, inil, inir;
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, i));
}
sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
for (int i = 0;i < m;i++) ed[i].id = i;
sort(wei.begin(), wei.end());
dsu.init(n);
solve(1, inf, ed, inil, inir);
vector<pii> ev;
for (int i = 0;i < m;i++) {
//debug(ed[i].u, ed[i].v, ed[i].w, ran[i].ff, ran[i].ss);
if (ran[i].ff) {
ev.push_back({ran[i].ff, i});
ev.push_back({ran[i].ss, i});
}
}
sort(ev.begin(), ev.end());
int q;
cin >> q;
vector<int> que(q);
multiset<int> se;
int ind = 0;
for (int i = 0;i < q;i++) {
cin >> que[i];
while (ind < ev.size() && ev[ind].ff <= que[i]) {
if (!on[ev[ind].ss]) {
se.insert(wei[ev[ind].ss]);
on[ev[ind].ss] = 1;
} else {
se.erase(se.find(wei[ev[ind].ss]));
}
ind++;
}
ll ans = 0;
for (int j:se) ans += abs(j - que[i]);
cout << ans << "\n";
}
//for (int i = m - 1;i >= 0;i--) debug(ed[i].u, ed[i].v, ed[i].w);
}
Compilation message
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:174:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | while (ind < ev.size() && ev[ind].ff <= que[i]) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
810 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
