#include "swap.h" #include <cstring> #include <vector> const int N = 100000, M = 200000; 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 ii[M], jj[M], 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]; char ok[N]; int find(int i) { return ds[i] < 0 ? i : find(ds[i]); } void join(int i, int j, char special) { i = find(i); j = find(j); if (i == j) { ok[i] = 1; return; } if (ds[i] > ds[j]) ds[i] = j, ok[j] |= ok[i] | special; else { if (ds[i] == ds[j]) ds[i]--; ds[j] = i, ok[i] |= ok[j] | special; } } int hh[M], n, m; void init(int n_, int m_, std::vector<int> II, std::vector<int> JJ, std::vector<int> WW) { int h; n = n_, m = m_; for (h = 0; h < m; h++) ii[h] = II[h], jj[h] = JJ[h], ww[h] = WW[h], hh[h] = h; sort(hh, 0, m); } int getMinimumFuelCapacity(int u, int v) { static int dd[N]; int h; memset(ds, -1, n * sizeof *ds); memset(dd, 0, n * sizeof *dd); memset(ok, 0, n * sizeof *ok); 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, dd[i] > 2 || dd[j] > 2); if (find(u) == find(v) && ok[find(u)]) return w; } return -1; }