#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int nax = 300005;
const int K = 23;
int fa[nax], front[nax], back[nax], val[nax];
bool chain[nax];
int N, M, id;
vector<pair<int, pair<int, int>>> edges; // (W, index)
int G[nax][2], sp[nax][K], dep[nax];
int find(int x) {
if (x == fa[x]) return x;
fa[x] = find(fa[x]);
return fa[x];
}
void dfs(int u, int f) {
if (!u) return;
dep[u] = dep[f] + 1;
sp[u][0] = f;
for (int i = 1; i < K; i++) sp[u][i] = sp[sp[u][i - 1]][i - 1];
for (int child = 0; child < 2; child++) {
dfs(G[u][child], u);
}
}
int lca(int u, int v) {
if (dep[v] >= dep[u]) swap(u, v);
for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] >= dep[v]) u = sp[u][i];
if (u == v) return u;
for (int i = K - 1; i >= 0; i--) if (dep[sp[u][i]] != dep[sp[v][i]]) u = sp[u][i], v = sp[v][i];
return sp[u][0];
}
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = _N; M = _M;
for (int i = 0; i < M; i++)
edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
sort(edges.begin(), edges.end());
for (int i = 0; i < nax; i++) fa[i] = i;
for (int i = 1; i <= N; i++) {
chain[i] = true;
front[i] = back[i] = i;
}
id = N;
for (int i = 0; i < M; i++) {
int w = edges[i].first;
int u = edges[i].second.first + 1;
int v = edges[i].second.second + 1;
int A = find(u), B = find(v);
if (A == B) {
if (chain[A]) {
int new_id = ++id;
fa[A] = new_id;
val[new_id] = w;
G[new_id][0] = A;
}
continue;
}
int new_id = ++id;
fa[A] = new_id;
fa[B] = new_id;
val[new_id] = w;
G[new_id][0] = A;
G[new_id][1] = B;
if (chain[A] && chain[B]) {
if (front[A] == v || back[A] == v) swap(A, B);
// connect u -> v
// x -> u -> v -> y
if (front[A] == u) swap(front[A], back[A]);
if (back[B] == v) swap(front[B], back[B]);
if (back[A] == u && front[B] == v) {
chain[new_id] = true;
front[new_id] = front[A];
back[new_id] = back[B];
}
}
}
dfs(id, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
X++; Y++;
int l = lca(X, Y);
if (!chain[l]) return val[l];
for (int i = K - 1; i >= 0; i--) {
if (sp[l][i] && chain[sp[l][i]]) {
l = sp[l][i];
}
}
if (l == id) return -1;
return val[sp[l][0]];
}
#include "grader.cpp"
Compilation message
/usr/bin/ld: /tmp/ccpnX1qR.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccd5ADSR.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
