| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1093743 | _8_8_ | 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.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 3;
#define int ll
int n, m, vis[N], timer = 0, p[N], f[N];
vector<array<int, 3>> e(N);
vector<vector<int>> tr;
vector<int> cur;
int id(int v, int u) {
vector<vector<pair<int,int>>> g(n + 1);
for(int i:cur) {
g[e[i][1]].push_back({e[i][2], i});
g[e[i][2]].push_back({e[i][1], i});
}
queue<int> q;
q.push(v);
++timer;
vis[v] = timer;
while(!q.empty()) {
int x = q.front();
q.pop();
// cout << x << ' ' << p[x] << '\n';
for(auto [to, i]:g[x]) {
// cout << to << "x\n";
if(vis[to] != timer) {
vis[to] = timer;
p[to] = x;
f[to] = i;
q.push(to);
}
}
}
int ret = 1e9;
while(u != v) {
ret = min(ret, f[u]);
u = p[u];
// cerr << u << ' ' << v << '\n';
}
return ret;
}
int P[N];
int get(int a) {
if(P[a] == a) return a;
return P[a] = get(P[a]);
}
bool merge(int a, int b) {
a = get(a);
b = get(b);
if(a == b) return false;
P[a] = b;
return true;
}
ll cost(vector<int> &x, int val) {
// cout << (int)x.size() << '\n';
ll ret = 0;
for(int i:x) {
ret += abs(val - e[i][0]);
}
return ret;
}
int l[N], r[N];
const int inf = (int)1e9;
void test() {
cin >> n >> m;
for(int i = 0;i < m; i++) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
l[i] = 0, r[i] = inf;
}
iota(P + 1, P + n + 1, 1);
sort(e.begin(), e.begin() + m);
int lst = 0;
for(int i = 0;i < m; i++) {
if(merge(e[i][2], e[i][1])) {
cur.push_back(i);
continue;
}
int j = id(e[i][1], e[i][2]);
ll val = (e[i][0] + e[j][0] + 1) / 2;
l[i] = val;
r[j] = val - 1;
for(int k = 0; k < (int)cur.size(); k++) {
if(cur[k] == j) {
cur.erase(cur.begin() + k);
break;
}
}
cur.push_back(i);
}
vector<array<int, 3>> o;
for(int i = 0; i < m; i++) {
o.push_back({l[i], r[i], e[i][0]});
}
sort(o.begin(), o.end());
multiset<int> L, R;
multiset<pair<int, int>> st;
ll _l = 0, _r = 0;
int q;
cin >> q;
int it = 0;
while(q--) {
int x;
cin >> x;
ll res = 0;
auto add = [&](int val) {
if(val <= x) {
_l += val;
L.insert(val);
} else {
_r += val;
R.insert(val);
}
};
auto del = [&](int val) {
if(L.find(val) != L.end()) {
L.erase(L.find(val));
_l -= val;
} else {
R.erase(R.find(val));
_r -= val;
}
};
auto f = [&](multiset<int> &t, ll s) {
res += abs(s - x * 1ll * (int)t.size());
};
while(it < m && o[it][0] <= x) {
st.insert(o[it][1], o[it][2]);
add(o[it][2]);
it++;
}
while(!st.empty()) {
auto [d, e] = (*st.begin());
if(d < x) {
del(e);
st.erase(st.find({d,e}));
} else {
break;
}
}
while(!R.empty()) {
int val = (*R.begin());
// cerr << val << ' ' << x << '\n';
if(val <= x) {
R.erase(R.find(val));
_r -= val;
add(val);
} else {
break;
}
}
f(L, _l);
f(R, _r);
cout << res << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}