#include "swap.h"
#include <cstring>
#include <vector>
const int N = 100000, M = 200000, INF = 0x3f3f3f3f;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ww[M];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[hh[j]] == ww[h])
j++;
else if (ww[hh[j]] < ww[h]) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
sort(hh, l, i);
l = k;
}
}
int ds[N], ww_[N], ww1[N];
int find(int i) {
return ds[i] < 0 ? i : find(ds[i]);
}
void join(int i, int j, int w, int special) {
i = find(i);
j = find(j);
if (i == j) {
ww1[i] = min(ww1[i], w);
return;
}
if (ds[i] > ds[j]) {
ds[i] = j, ww_[i] = w;
ww1[j] = min(ww1[j], ww1[i]);
if (special)
ww1[j] = min(ww1[j], w);
} else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i, ww_[j] = w;
ww1[i] = min(ww1[i], ww1[j]);
if (special)
ww1[i] = min(ww1[i], w);
}
}
int n, m;
void init(int n_, int m_, std::vector<int> ii, std::vector<int> jj, std::vector<int> WW) {
static int hh[M], dd[N];
int h;
n = n_, m = m_;
for (h = 0; h < m; h++)
ww[h] = WW[h], hh[h] = h;
sort(hh, 0, m);
memset(dd, 0, n * sizeof *dd);
memset(ds, -1, n * sizeof *ds);
memset(ww_, 0x3f, n * sizeof *ww_);
memset(ww1, 0x3f, n * sizeof *ww1);
for (h = 0; h < m; h++) {
int i = ii[hh[h]], j = jj[hh[h]], w = ww[hh[h]];
dd[i]++, dd[j]++;
join(i, j, w, dd[i] > 2 || dd[j] > 2);
}
}
int getMinimumFuelCapacity(int i, int j) {
long long w1 = 0;
while (i != j)
if (ww_[i] < ww_[j])
w1 = ww_[i], i = ds[i];
else
w1 = ww_[j], j = ds[j];
while (i >= 0) {
if (ww1[i] != INF)
return max(w1, ww1[i]);
i = ds[i];
}
return -1;
}
Compilation message
paint.cpp:1:10: fatal error: swap.h: No such file or directory
1 | #include "swap.h"
| ^~~~~~~~
compilation terminated.
