#include <bits/stdc++.h>
#include "swap.h"
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 10;
struct edge {
int from, to, w;
edge () {}
edge (int a, int b, int c) {
from = a,
to = b,
w = c;
}
};
bool cmp (edge e1, edge e2) {
return e1.w < e2.w;
}
vector<edge> roads;
int SZ;
int kol;
int p[N];
int sz[N];
int st[N];
int ed[N];
int dist[N];
bool cycle[N];
vector<pii> gr[N];
void init_dsu () {
for (int i = 0; i < N; ++i)
p[i] = i,
st[i] = i,
ed[i] = i;
}
int get (int u) {
if (u != p[u])
p[u] = get(p[u]);
return p[u];
}
void join (int u, int v, int w) {
int u1 = u, v1 = v;
u = get(u);
v = get(v);
if (u == v) {
++kol;
// cout << "add_road " << kol << ' ' << u << ' ' << w << '\n';
gr[kol].push_back({u, w});
p[u] = kol;
cycle[kol] = 1;
return;
}
++kol;
cycle[kol] = (cycle[u] | cycle[v]);
if ((u1 == st[u] || u1 == ed[u]) && (v1 == st[v] || v1 == ed[v])) {
set<int> all;
all.insert(st[u]);
all.insert(ed[u]);
all.insert(st[v]);
all.insert(ed[v]);
if (all.size() > 2) {
all.erase(st[u]);
all.erase(st[v]);
}
st[kol] = (*all.begin());
ed[kol] = (*all.rbegin());
} else {
cycle[kol] = 1;
}
// cout << "add_road " << kol << ' ' << u << ' ' << v << ' ' << w << '\n';
gr[kol].push_back({u, w});
gr[kol].push_back({v, w});
p[u] = kol;
p[v] = kol;
}
int timer;
int tin[N];
int tout[N];
int lc[N][20];
int mx[N][20];
void dfs(int city, int pr, int ls) {
// cout << "dfs("<<city<<")\n";
tin[city] = ++timer;
lc[city][0] = pr;
mx[city][0] = ls;
for (int i = 1; i < 20; ++i) {
lc[city][i] = lc[lc[city][i - 1]][i - 1];
mx[city][i] = max(mx[city][i - 1], mx[lc[city][i - 1]][i - 1]);
}
for (auto i : gr[city]) {
dist[i.fi] = dist[city] + 1;
dfs(i.fi, city, i.se);
}
tout[city] = ++timer;
}
bool upper(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int get_on_dist (int u, int x) {
int abu = 0;
for (int i = 19; i >= 0; --i)
if (abu + (1 << i) < x && lc[u][i])
u = lc[u][i];
return u;
}
bool check_lca (int u, int v, int lca) {
// cout << "check_lca u, v, lca = " << u << ' ' << v << ' ' << lca << ' ' << upper(lca, u) << ' ' << upper(lca, v) << '\n';
if (upper(lca, u) && upper(lca, v))
return 1;
return 0;
}
int get_max (int lca, int v) {
if (lca == v)
return 0;
int res = 0;
for (int i = 19; i >= 0; --i)
if (lc[v][i] && !upper(lc[v][i], lca)) {
res = max(res, mx[v][i]);
v = lc[v][i];
}
return max(res, mx[v][0]);
}
void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
kol = SZ = n;
for (int i = 0; i < m; ++i) {
u[i]++;
v[i]++;
edge e(u[i], v[i], w[i]);
roads.push_back(e);
}
init_dsu();
sort(roads.begin(), roads.end(), cmp);
for (edge e : roads)
join(e.from, e.to, e.w);
dfs(kol, 0, 0);
}
int getMinimumFuelCapacity (int u, int v) {
if (u == v)
return -1;
++u;
++v;
int l = 0, r = kol;
while (l + 1 < r) {
int mid = (l + r) >> 1;
int lca = get_on_dist(u, mid);
// cout << "mid, lca = " << l << ' ' << r << ' ' << mid << ' ' << lca << ' ' << check_lca(u, v, lca) << ' ' << cycle[lca] << '\n';
if (!check_lca(u, v, lca) || !cycle[lca]) {
l = mid;
} else {
r = mid;
}
}
if (r == kol)
return -1;
int lca = get_on_dist(u, r);
// cout << "u, v, lca = " << u << ' ' << v << ' ' << lca << '\n';
return max(get_max(lca, u), get_max(lca, v));
}
// signed main () {
// // ios_base::sync_with_stdio(0);
// // cin.tie(0), cout.tie(0);
// int n, m, q;
// cin >> n >> m;
// vector<int> u(m), v(m), w(m);
// for (int i = 0; i < m; ++i)
// cin >> u[i] >> v[i] >> w[i];
// init(n, m, u, v, w);
// cin >> q;
// while (q--) {
// int x, y;
// cin >> x >> y;
// cout << getMinimumFuelCapacity(x, y) << '\n';
// }
// return 0;
// }
// 5 6
// 0 1 4
// 0 2 4
// 2 1 1
// 2 3 3
// 1 3 2
// 1 4 10
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Incorrect |
657 ms |
67388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
19548 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19548 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
19548 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
