// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 19;
constexpr int MOD = 1e9+7;
int n,m,q;
struct DSU {
vector<int> p, sz;
void reset(int s) {
p.assign(s + 3, 0);
sz.assign(s + 3, 1);
}
void make_set(int x) {
p[x] = x;
}
int find_set(int x) {
return (p[x] == x) ? x : p[x] = find_set(p[x]);
}
bool union_set(int x, int y) {
x = find_set(x); y = find_set(y);
if(x == y) return 0;
if(sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
p[y] = x;
return 1;
}
};
vector<vector<int> > adj;
vector<vector<int> > anc;
vector<vector<int> > pcost, cst;
vector<int> dep;
vector<array<array<int, 2>, 3> > cost3;
vector<array<int,3> > edges;
DSU ds;
void prec(int node, int par, vector<vector<array<int,2> > > &tmp) {
vector<array<int,2> >::iterator mnc;
anc[node][0] = par;
int mn = INF;
for(auto itr = tmp[node].begin(); itr != tmp[node].end(); ) {
auto &c = *itr;
if(c[0] == par) {
pcost[node][0] = pcost[n + node][0] = c[1];
itr = tmp[node].erase(itr);
continue;
}
if(mn > c[1]) {
mn = c[1];
mnc = itr;
}
dep[c[0]] = dep[c[0] + n] = dep[node] + 1;
prec(c[0], node, tmp);
itr++;
}
if(tmp[node].empty()) return;
adj[n + node].pb((*mnc)[0]);
anc[(*mnc)[0]][0] = n + node;
cst[node][0] = mn;
cst[n + node][0] = INF;
for(auto itr = tmp[node].begin(); itr != tmp[node].end(); itr++) {
if(itr == mnc) continue;
cst[n + node][0] = min(cst[n + node][0], (*itr)[1]);
adj[node].pb((*itr)[0]);
}
}
void calc() {
for(int k = 1; k < LGN; k++) {
for(int i = 0; i <= 2*n; i++) {
anc[i][k] = anc[anc[i][k - 1]][k - 1];
pcost[i][k] = max(pcost[i][k - 1], pcost[anc[i][k - 1]][k - 1]);
cst[i][k] = min(cst[i][k - 1], cst[anc[i][k - 1]][k - 1]);
}
}
}
int kth_anc(int a, int k) {
for(int i = 0; i < LGN; i++) {
if(k & (1 << i)) {
a = anc[a][i];
}
}
return a;
}
int lca(int a, int b) {
if(dep[a] > dep[b]) swap(a, b);
b = kth_anc(b, dep[b] - dep[a]);
if(a == b) return a;
for(int k = LGN - 1; k>=0; k--) {
if(anc[a][k] != anc[b][k]) {
a = anc[a][k];
b = anc[b][k];
}
}
return anc[a][0];
}
int get_dist(int a, int b) {
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int get_cst(int a, int b) {
// b is anc of a
// [a, b)
int ans = INF;
for(int k = LGN - 1; k>=0; k--) {
if(dep[anc[a][k]] > dep[b]) {
ans = min(ans, cst[a][k]);
a = anc[a][k];
}
}
return ans;
}
int get_pcost(int a, int b) {
// b is anc of a
// [a, b)
int ans = 0;
for(int k = LGN - 1; k>=0; k--) {
if(dep[anc[a][k]] > dep[b]) {
ans = max(ans, pcost[a][k]);
a = anc[a][k];
}
}
return ans;
}
int get_lca_cost(int a, int b, int lc) {
if(a != lc) a = kth_anc(a, dep[a] - dep[lc] - 1);
if(b != lc) b = kth_anc(b, dep[b] - dep[lc] - 1);
for(auto &c : cost3[lc]) {
if(c[0] != a && c[0] != b) return c[1];
}
return INF;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
edges.resize(M);
adj.assign(2 * N + 5, vector<int>());
for(int i = 0; i < M; i++) {
edges[i] = {W[i], U[i], V[i]};
}
sort(all(edges));
ds.reset(N);
for(int i = 0; i < N; i++) ds.make_set(i);
vector<vector<array<int,2> > > tmp(N, vector<array<int,2> >());
pcost.assign(2*N + 5, vector<int>(LGN, 0));
cst.assign(2*N + 5, vector<int>(LGN, INF));
anc.assign(2*N + 5, vector<int>(LGN, 2 * N));
anc[2*N][0] = 2 * N;
dep.assign(2*N + 5, 0);
for(auto &c : edges) {
if(ds.union_set(c[1], c[2])) {
tmp[c[1]].pb({c[2], c[0]});
tmp[c[2]].pb({c[1], c[0]});
}
}
cost3.resize(2*N + 5);
for(int i = 0; i < 2*N + 5; i++) {
REP(j, 3) cost3[i][j] = {0, INF};
}
for(int i = 0; i < N; i++) {
sort(all(tmp[i]), [](array<int,2> &x, array<int,2> &y) {
return x[1] < y[1];
});
for(int j = 0; j < min(3, (int)tmp[i].size()); j++) {
cost3[i][j] = cost3[i + N][j] = tmp[i][j];
}
}
prec(0, 2*N, tmp);
calc();
}
int getMinimumFuelCapacity(int X, int Y) {
int u, v, mn = INF;
REP(i, 2) {
REP(j, 2) {
int tmp = get_dist(X + i * n, Y + j * n);
if(tmp < mn) {
mn = tmp;
u = X + i * n;
v = Y + j * n;
}
}
}
int lc = lca(u, v);
// cout << "u:" << u << " v:" << v << " lc:" << lc << "\n";
int ans = max(get_pcost(v, lc), get_pcost(u, lc));
int cost = INF;
if(lc != u) cost = min(cost, get_cst(anc[u][0], lc));
if(lc != v) cost = min(cost, get_cst(anc[v][0], lc));
cost = min(cost, get_lca_cost(u, v, lc));
ans = max(ans, cost);
if(ans == INF) return -1;
return ans;
}
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:222:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
222 | cost = min(cost, get_lca_cost(u, v, lc));
| ~~~~~~~~~~~~^~~~~~~~~~
swap.cpp:222:34: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
390 ms |
93092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
