#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 3> p3i;
const int MXN = 505, MXM = 100005, MXQ = 1000005;
int n, m, q;
int eu[MXM], ev[MXM], ew[MXM], qry[MXQ];
struct DSU {
int p[MXN];
void init(int n) {
fill(p + 1, p + n + 1, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool onion(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y];
p[y] = x;
return true;
}
};
namespace SB12 {
p3i edge[MXN];
DSU dsu;
int calc(int x) {
FOR(i, 0, m) edge[i] = {abs(x - ew[i]), eu[i] ,ev[i]};
sort(edge, edge + m, greater<p3i>());
dsu.init(n);
int ans = 0;
FOR(i, 0, m) {
auto &[w, u, v] = edge[i];
if (dsu.onion(u, v)) ans += w;
}
return ans;
}
void solve() {
FOR(i, 0, q) cout << calc(qry[i]) << '\n';
}
}
namespace SB3 {
p3i edge[MXM];
vector<pii> op;
int ans[MXQ];
int d;
bool check() {
FOR(i, 0, m) if (ev[i] != eu[i] + 1) return false;
return true;
}
int process(int l, int r) {
vector<int> v;
int sml = INT_MAX;
FOR(i, l, r) {
v.push_back(edge[i][2]);
}
sort(v.begin(), v.end());
for (auto &i : v) {
op.push_back(mp(i, -1LL));
op.push_back(mp(i, -1LL));
}
FOR(i, 1, v.size()) {
int x = v[i - 1], y = v[i];
op.push_back(mp(x + (y - x) / 2, -2LL));
op.push_back(mp(x + (y - x) / 2 + (y - x) % 2, -2LL));
}
return v.front();
}
void solve() {
assert(check());
FOR(i, 0, m) edge[i] = {eu[i], ev[i], ew[i]};
sort(edge, edge + m);
int cost = 0;
for (int i = 0, j = 0; i < m; i = j) {
while (j < m && edge[i][0] == edge[j][0]) j++;
cost += process(i, j);
}
FOR(i, 0, q) op.push_back(mp(qry[i], i));
sort(op.begin(), op.end());
int time = 0;
d = -(n - 1);
for (auto &[t, id] : op) {
debug(t, id);
cost += (t - time) * d;
time = t;
if (id == -2) {
d--;
} else if (id == -1) {
d++;
} else {
ans[id] = cost;
}
}
FOR(i, 0, q) cout << ans[i] << '\n';
}
}
void miku() {
cin >> n >> m;
FOR(i, 0, m) {
cin >> eu[i] >> ev[i] >> ew[i];
}
cin >> q;
FOR(i, 0, q) cin >> qry[i];
if (q <= 10) SB12::solve();
else SB3::solve();
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
reconstruction.cpp: In function 'long long int SB3::process(long long int, long long int)':
reconstruction.cpp:79:13: warning: unused variable 'sml' [-Wunused-variable]
79 | int sml = INT_MAX;
| ^~~
reconstruction.cpp: In function 'void SB3::solve()':
reconstruction.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
reconstruction.cpp:110:13: note: in expansion of macro 'debug'
110 | debug(t, id);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
