| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 877009 | 406 | Reconstruction Project (JOI22_reconstruction) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2")
//besmellah
//accept sho :D
//de akhe mashti NM * DSU nabayad AC she?
//oon moghe NM log bood hichi
//alan vali NM DSU ee
//man ozrkhahi mikonam az tarah
//che bug sangini zadim
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
//#define int long long
using namespace std;
using ar = array<int, 2>;
using ar4 = array<int, 4>;
const int M = 1e5 + 5, N = 505, Q = 1e6 + 5;
const long long INF = 1ll << 30;
inline namespace dsu {
int dpr[N];
void init() {
memset(dpr, -1, sizeof dpr);
}
int gpr(int x) {
return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
}
bool merge(int u, int v) {
u = gpr(u), v = gpr(v);
if (u == v) return false;
if (dpr[u] < dpr[v]) swap(u, v);
dpr[v] += dpr[u];
dpr[u] = v;
return true;
}
}
inline bool cmp(const ar5 &X, const ar5 &Y) {
return X[0] < Y[0];
}
vector<ar> adj[N];
int n, m, WD[N];
short pr[N], T, st[N], fn[N];
ar4 E[M];
vector<ar4> undo, bk, Es, to_calc;
void dfs(int v, int p) {
seen[v] = true;
st[v] = T++;
for (auto [u, w]: adj[v]) if (u != p) {
WD[u] = w;
pr[u] = v;
dfs(u, v);
}
fn[v] = T++;
}
ar4 validate(vector<ar4> &E) {
vector<ar4> ok;
ok.reserve(E.size());
dsu::init();
ar4 del = {-1, -1, -1, -1};
for (auto A: E) {
auto [w, u, v, t] = A;
if (dsu::merge(u, v))
ok.push_back(A);
else del = A;
}
E.swap(ok);
return del;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
FOR(i, 0, m) {
cin >> E[i][1] >> E[i][2] >> E[i][0];
--E[i][1], --E[i][2];
if (E[i][1] > E[i][2]) swap(E[i][1], E[i][2]);
}
sort(E, E + m);
for (int i = m - 1; i >= 0; --i) {
auto &[w, u, v, t] = E[i];
t = 1;
bk.insert(lower_bound(bk.begin(), bk.end(), E[i], cmp), E[i]);
undo.push_back(validate(bk));
}
int q; cin >> q;
int p = 0, minl = -INF;
long long td, W, cnt = 0;
//ar3 dar vaghe ar4-e
vector<ar4> fr;
FOR(i, 0, q) {
int x; cin >> x;
bool t = false;
while (p < m && x >= E[p][0]) {
ar4 X = {-E[p][0], E[p][1], E[p][2], , 0};
fr.insert(lower_bound(fr.begin(), fr.end(), X, cmp), X);
auto U = undo.back();
undo.pop_back();
bk.erase(find_if(bk.begin(), bk.end(), [&](const auto &X) {
return X[0] == E[p][0] && X[1] == E[p][1] && X[2] == E[p][2];
}));
if (U[0] != -1)
bk.insert(lower_bound(bk.begin(), bk.end(), U, cmp), U);
++p;
t = true;
}
if (t || x >= minl) { //build_mst() (M bar hadeaksar)
assert(++cnt <= 5 * m);
validate(fr);
dsu::init();
W = td = 0;
minl = INF;
//al = bk + fr (bt)
vector<ar4> al; //badihish
al.resize(fr.size() + bk.size());
for (auto &A: fr) A[0] += x;
for (auto &A: bk) A[0] -= x;
merge(fr.begin(), fr.end(), bk.begin(), bk.end(), al.begin(), cmp);
for (auto &A: fr) A[0] -= x;
for (auto &A: bk) A[0] += x;
//sort(al.begin(), al.end());
FOR(i, 0, n) adj[i].clear();
for (auto A: al) {
auto &[w, u, v, t] = A;
w = (t ? w + x : x - w);
if (dsu::merge(u, v)) {
W += (t ? w : -w);
td += (t ? -1 : +1);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
else if (t) {
to_calc.push_back(A);
}
else {
A[0] *= -1;
fr.erase(find(fr.begin(), fr.end(), A));
}
}
seen = 0;
T = 0;
FOR(i, 0, n) if (!seen[i])
dfs(i, i);
for (auto A: to_calc) {
auto [w, u, v, t] = A;
int W = INF;
minl = min(W + w >> 1, minl);
}
to_calc.clear();
}
cout << 1ll * td * x + W << '\n';
}
return 0;
}