#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct dsu {
vector<int> p, sze;
int comps;
dsu(int n) : p(n+1), sze(n+1), comps(n) {
for (int i = 0; i <= n; i++) {
p[i] = i, sze[i] = 1;
}
}
int get(int v) {
return v==p[v]?v:p[v]=get(p[v]);
}
int size(int v) {
return sze[get(v)];
}
bool merge(int a, int b) {
if ((a=get(a)) == (b=get(b))) return 0;
if (sze[a]<sze[b]) swap(a, b);
sze[a] += sze[b], p[b] = a;
comps--;
return 1;
}
};
void test_case() {
int n, m;
cin >> n >> m;
vector<ar<int, 3>> edges(m);
for (auto &x : edges) cin >> x[0] >> x[1] >> x[2];
vector<int> lst;
vector<int> order(m);
auto cmp = [&](int x, int y) {
return edges[x][2] != edges[y][2] ? edges[x][2] < edges[y][2] : x < y;
};
iota(all(order), 0);
sort(all(order), cmp);
vector<vector<int>> suff(m), pref(m);
{
dsu d(n);
vector<int> cur;
for (int i = 0; i < m; i++) {
auto [x, y, w] = edges[order[i]];
if (d.merge(x, y)) {
cur.emplace_back(order[i]);
}
}
suff[0] = cur;
for (int i = 1; i < m; i++) {
auto mn = min_element(all(cur), cmp);
if (*mn == order[i-1]) {
d = dsu(n);
cur.erase(mn);
for (int idx : cur) {
d.merge(edges[idx][0], edges[idx][1]);
}
for (int j = i; j < m; j++) {
int pos = order[j];
if (d.merge(edges[pos][0], edges[pos][1])) {
cur.insert(upper_bound(all(cur), pos, cmp), pos);
break;
}
}
}
suff[i] = cur;
}
}
{
dsu d(n);
vector<int> cur;
for (int i = m-1; i >= 0; i--) {
auto [x, y, w] = edges[order[i]];
if (d.merge(x, y)) {
cur.emplace_back(order[i]);
}
}
pref[m-1] = cur;
for (int i = m-2; i >= 0; i--) {
auto mx = max_element(all(cur), cmp);
if (*mx == order[i+1]) {
d = dsu(n);
cur.erase(mx);
for (int idx : cur) {
d.merge(edges[idx][0], edges[idx][1]);
}
for (int j = i; j >= 0; j--) {
int pos = order[j];
if (d.merge(edges[pos][0], edges[pos][1])) {
cur.insert(upper_bound(all(cur), pos, cmp), pos);
break;
}
}
}
pref[i] = cur;
}
}
int q; cin >> q;
const int INF = 2e9;
while (q--) {
int x; cin >> x;
int l = 0, r = m-1, ans = -1;
while (l <= r) {
int mid = (l+r)/2;
if (x >= edges[order[mid]][2]) ans = mid, l = mid+1;
else r = mid-1;
}
/*
{
int L = ans, R = ans + 1, added = 0;
dsu d(n);
ll ans2 = 0;
while (added < n-1) {
int costA = L >= 0 ? x - edges[order[L]][2] : INF;
int costB = R < m ? edges[order[R]][2] - x : INF;
if (costA < costB) {
if (d.merge(edges[order[L]][0], edges[order[L]][1])) {
cout << order[L] << " ";
ans2 += costA, added++;
}
L--;
}
else {
if (d.merge(edges[order[R]][0], edges[order[R]][1])) {
cout << order[R] << " ";
ans2 += costB, added++;
}
R++;
}
}
cout << '\n';
cout << ans2 << '\n';
continue;
}
*/
int a = ans >= 0 ? sz(pref[ans]) - 1 : 0, b = 0, added = 0;
dsu d(n);
ll ans2 = 0;
while (added < n-1) {
int costA = ans >= 0 && a >= 0 ? x - edges[pref[ans][a]][2] : INF;
int costB = ans + 1 < m && b < sz(suff[ans+1]) ? edges[suff[ans+1][b]][2] - x : INF;
assert(costA >= 0);
assert(costB >= 0);
if (costA < costB) {
auto [u, v, w] = edges[pref[ans][a]];
if (d.merge(u, v)) added++, ans2 += costA;
a--;
}
else {
auto [u, v, w] = edges[suff[ans+1][b]];
if (d.merge(u, v)) added++, ans2 += costB;
b++;
}
}
cout << ans2 << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while (t--) test_case();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
5094 ms |
403668 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
