#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
#include "swap.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 19;
const long double EPS = 1e-9, PI = acos(-1);
struct dsu
{
int n;
vector<int> p, deg, res;
vector<vector<int>> has;
dsu() {}
dsu(int in)
{
n = in;
p.resize(n);
iota(p.begin(), p.end(), 0);
deg.resize(n);
res.resize(n, INF);
has.resize(n);
for (int i = 0; i < n; i++)
{
has[i] = { i };
}
}
bool unite(int a, int b, int idx)
{
deg[a]++;
deg[b]++;
bool thr = (deg[a] >= 3 || deg[b] >= 3);
a = p[a];
b = p[b];
if (a == b)
{
if (res[a] == INF)
{
for (auto& i : has[a])
{
res[i] = idx;
}
}
return false;
}
if (has[a].size() < has[b].size())
{
swap(a, b);
}
if ((thr || res[b] != INF) && res[a] == INF)
{
for (auto& i : has[a])
{
res[i] = idx;
}
}
if ((thr || res[a] != INF) && res[b] == INF)
{
for (auto& i : has[b])
{
res[i] = idx;
}
}
for (auto& i : has[b])
{
has[a].push_back(i);
p[i] = a;
}
has[b] = {};
}
int get(int v)
{
return res[v];
}
};
struct edge
{
int to, idx;
};
const int N = 1e5 + 5;
int n, m;
vector<edge> g[N];
vector<int> binup[N], maxidx[N], h;
vector<int> ew;
dsu kek;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N;
m = M;
vector<tuple<int, int, int>> e;
e.resize(m);
for (int i = 0; i < m; i++)
{
e[i] = { W[i], U[i], V[i] };
}
sort(e.begin(), e.end());
ew.resize(m);
for (int i = 0; i < m; i++)
{
ew[i] = get<0>(e[i]);
}
kek = dsu(n);
for (int i = 0; i < m; i++)
{
auto& [w, a, b] = e[i];
if (kek.unite(a, b, i))
{
g[a].push_back({ b, i });
g[b].push_back({ a, i });
}
}
fill_n(binup, n, vector<int>(LOG));
fill_n(maxidx, n, vector<int>(LOG, INF));
h.resize(n);
auto build = [&](auto build, int v, int p) -> void
{
if (p == -1)
{
h[v] = 0;
binup[v][0] = 0;
maxidx[v][0] = -1;
}
else
{
h[v] = h[p] + 1;
binup[v][0] = p;
}
for (int i = 1; i < LOG; i++)
{
binup[v][i] = binup[binup[v][i - 1]][i - 1];
maxidx[v][i] = max(maxidx[v][i - 1], maxidx[binup[v][i - 1]][i - 1]);
}
for (auto& i : g[v])
{
if (i.to == p)
{
continue;
}
maxidx[i.to][0] = i.idx;
build(build, i.to, v);
}
};
build(build, 0, -1);
}
int getMinimumFuelCapacity(int X, int Y)
{
auto get_la = [&](int v, int x) -> int
{
for (int i = LOG - 1; i > -1; i--)
{
if (h[v] - h[binup[v][i]] <= x)
{
x -= h[v] - h[binup[v][i]];
v = binup[v][i];
}
}
return v;
};
auto get_lca = [&](int a, int b) -> int
{
if (h[a] < h[b])
{
swap(a, b);
}
a = get_la(a, h[a] - h[b]);
if (a == b)
{
return a;
}
for (int i = LOG - 1; i > -1; i--)
{
if (binup[a][i] != binup[b][i])
{
a = binup[a][i];
b = binup[b][i];
}
}
return binup[a][0];
};
int a = X, b = Y, c = get_lca(a, b);
int ans = min(kek.get(a), kek.get(b));
auto get_up = [&](int& ver) -> void
{
for (int i = LOG - 1; i > -1; i--)
{
if (h[binup[ver][i]] >= h[c])
{
ans = max(ans, maxidx[ver][i]);
ver = binup[ver][i];
}
}
};
get_up(a);
get_up(b);
if (ans == INF)
{
return -1;
}
return ew[ans];
}
/*
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
printf("%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
*/
/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/
Compilation message
swap.cpp: In member function 'bool dsu::unite(int, int, int)':
swap.cpp:97:19: warning: control reaches end of non-void function [-Wreturn-type]
97 | has[b] = {};
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
14660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
