#include "swap.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <algorithm>
#include <cassert>
#include <numeric>
using namespace std;
#define all(x) x.begin(), x.end()
const int maxn = 1e5;
const int inf = 2e9;
struct dsu {
int p[maxn];
int sz[maxn];
void init(int n) {
iota(p, p + n, 0);
fill(sz, sz + n, 1);
}
int c(int v) {
return (v == p[v] ? v : p[v] = c(p[v]));
}
int szz(int v) {
return sz[c(v)];
}
void unite(int u, int v) {
u = c(u);
v = c(v);
if (u == v) {
return;
}
p[u] = v;
sz[v] += sz[u];
}
};
vector<pair<int, pair<int, int>>> e;
int n;
vector<pair<int, int>> g[maxn];
vector<pair<int, int>> gg[maxn];
int timer = 0;
int tin[maxn];
int tout[maxn];
int up[20][maxn];
int cup[20][maxn];
int mp[20][maxn];
int cyc[20][maxn];
int cycleCost[maxn];
int minE[maxn];
vector<int> w;
bool isParent(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int len(int u, int v) {
int ans = inf;
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][u], v)) {
ans = min(ans, cup[i][u]);
u = up[i][u];
}
}
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][v], u)) {
ans = min(ans, cup[i][u]);
v = up[i][v];
}
}
int t = inf;
if (!isParent(u, v)) {
t = cup[0][u];
} else {
t = cup[0][v];
}
return min(ans, t);
}
int go(int u, int v) {
int ans = 0;
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][u], v)) {
ans = max(ans, mp[i][u]);
u = up[i][u];
}
}
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][v], u)) {
ans = max(ans, mp[i][u]);
v = up[i][v];
}
}
int t = 0;
if (!isParent(u, v)) {
t = mp[0][u];
}
if (!isParent(v, u)) {
t = max(t, mp[0][v]);
}
return max(ans, t);
}
int cost(int u, int v) {
return inf;
int ans = inf;
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][u], v)) {
ans = min(ans, cyc[i][u]);
u = up[i][u];
}
}
for (int i = 19; i >= 0; --i) {
if (!isParent(up[i][v], u)) {
ans = min(ans, cyc[i][u]);
v = up[i][v];
}
}
return ans;
}
void dfs(int v, int p, int q) {
up[0][v] = p;
for (int i = 1; i < 20; ++i) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
for (int j = 0; j < 20; ++j) {
cup[j][v] = inf;
mp[j][v] = 0;
}
if (v > 0) {
int ptr = 0;
while (ptr < gg[p].size() && gg[p][ptr] == make_pair(v, q)) ++ptr;
if (ptr < gg[p].size()) {
cup[0][v] = w[gg[p][ptr].second];
}
for (int j = 1; j < 20; ++j) {
cup[j][v] = min(cup[j - 1][v], cup[j - 1][up[j - 1][v]]);
}
}
if (q != -1) {
mp[0][v] = w[q];
for (int j = 1; j < 20; ++j) {
mp[j][v] = max(mp[j - 1][v], mp[j - 1][up[j - 1][v]]);
}
}
tin[v] = timer++;
for (auto [u, w] : g[v]) {
if (u != p) {
dfs(u, v, w);
}
}
tout[v] = timer++;
}
bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
if (w[a.first] != w[b.first]) {
return w[a.first] < w[b.first];
}
return a.second < b.second;
}
bool cmp1(pair<int, int> a, pair<int, int> b) {
if (w[a.second] != w[b.second]) {
return w[a.second] < w[b.second];
}
return a.first < b.first;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
w = W;
for (int i = 0; i < M; ++i) {
e.push_back({ i, { U[i], V[i] } });
gg[U[i]].push_back({ V[i], i });
gg[V[i]].push_back({ U[i], i });
}
for (int i = 0; i < N; ++i) {
sort(all(gg[i]), cmp1);
}
sort(all(e), cmp);
dsu ds;
ds.init(N);
for (int i = 0; i < M; ++i) {
auto [u, v] = e[i].second;
if (ds.c(u) != ds.c(v)) {
g[u].push_back({ v, e[i].first });
g[v].push_back({ u, e[i].first });
ds.unite(u, v);
}
}
// calc cycles
dfs(0, 0, -1);
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = max(go(X, Y), min(len(X, Y), cost(X, Y)));
return (ans == inf ? -1 : ans);
}
Compilation message
swap.cpp: In function 'void dfs(int, int, int)':
swap.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | while (ptr < gg[p].size() && gg[p][ptr] == make_pair(v, q)) ++ptr;
| ~~~~^~~~~~~~~~~~~~
swap.cpp:145:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | if (ptr < gg[p].size()) {
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5972 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
