| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1258725 | cpismylifeOwO | Swapping Cities (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#ifndef cpismylifeOwO
#include <swap.h>
#endif // cpismylifeOwO
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;
int ni, mi;
vector<int> Ui, Vi, Wi;
#ifdef cpismylifeOwO
void Inp()
{
cin >> ni >> mi;
for (int x = 1; x <= mi; x++)
{
int u, v, w;
cin >> u >> v >> w;
Ui.push_back(u);
Vi.push_back(v);
Wi.push_back(w);
}
}
#endif // cpismylifeOwO
struct Edge
{
int u, v, w;
bool operator < (const Edge& other) const
{
return this->w < other.w;
}
};
int n, m;
Edge edges[MaxN];
vector<int> child[MaxN];
int parents[MaxN];
int sz[MaxN];
int root[MaxN];
bool isline[MaxN];
int st[MaxN];
int ed[MaxN];
int FindSet(int p)
{
if (parents[p] == p)
{
return p;
}
parents[p] = FindSet(parents[p]);
return parents[p];
}
bool UnionSet(int a, int b, int r)
{
int pa = FindSet(a), pb = FindSet(b);
if (pa == pb)
{
root[pa] = r;
isline[pa] = false;
return !isline[pa];
}
if (sz[pa] < sz[pb])
{
swap(pa, pb);
swap(a, b);
}
isline[pa] &= isline[pb];
if (isline[pa])
{
if ((st[pa] == a || st[pa] == b) && (st[pb] == a || st[pb] == b || ed[pb] == a || ed[pb] == a))
{
st[pa] = st[pb] ^ ed[pb] ^ st[pa] ^ a ^ b;
}
else if ((ed[pa] == a || ed[pa] == b) && (st[pb] == a || st[pb] == b || ed[pb] == a || ed[pb] == a))
{
ed[pa] = st[pb] ^ ed[pb] ^ ed[pa] ^ a ^ b;
}
else
{
isline[pa] = false;
}
}
root[pa] = r;
sz[pa] += sz[pb];
parents[pb] = pa;
return !isline[pa];
}
bool good[MaxN];
int BinLift[MaxLog][MaxN];
int par[MaxN];
int h[MaxN];
void PreDFS(int u)
{
for (int x : child[u])
{
h[x] = h[u] + 1;
par[x] = u;
PreDFS(x);
}
}
void Build()
{
for (int x = 1; x <= n + m; x++)
{
BinLift[0][x] = par[x];
}
for (int x = 1; x < MaxLog; x++)
{
for (int y = 1; y <= n + m; y++)
{
BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
}
}
}
int LCA(int u, int v)
{
if (h[u] != h[v])
{
if (h[u] > h[v])
{
swap(u, v);
}
int k = h[v] - h[u];
for (int x = MaxLog - 1; x >= 0; x--)
{
if (k & (1 << x))
{
v = BinLift[x][v];
}
}
}
if (u == v)
{
return v;
}
for (int x = MaxLog - 1; x >= 0; x--)
{
if (BinLift[x][u] != BinLift[x][v])
{
u = BinLift[x][u];
v = BinLift[x][v];
}
}
return par[u];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
m = M;
for (int x = 0; x < m; x++)
{
edges[x + 1].u = U[x] + 1;
edges[x + 1].v = V[x] + 1;
edges[x + 1].w = W[x];
}
sort(edges + 1, edges + m + 1);
for (int x = 1; x <= n; x++)
{
parents[x] = x;
sz[x] = 1;
isline[x] = true;
st[x] = ed[x] = x;
root[x] = x;
}
for (int x = 1; x <= m; x++)
{
int u = FindSet(edges[x].u), v = FindSet(edges[x].v);
if (u == v)
{
child[x + n].push_back(root[u]);
good[x + n] = UnionSet(edges[x].u, edges[x].v, x + n);
}
else
{
child[x + n].push_back(root[u]);
child[x + n].push_back(root[v]);
good[x + n] = UnionSet(edges[x].u, edges[x].v, x + n);
}
}
PreDFS(n + m);
Build();
good[0] = true;
}
int getMinimumFuelCapacity(int X, int Y)
{
int u = X + 1, v = Y + 1, lca = LCA(u, v);
//cout << good[lca] << " ";
if (good[lca])
{
return edges[lca - n].w;
}
for (int x = MaxLog - 1; x >= 0; x--)
{
int k = BinLift[x][lca];
if (!good[k])
{
lca = k;
}
}
lca = par[lca];
if (lca == 0)
{
return -1;
}
return edges[lca - n].w;
}
#ifdef cpismylifeOwO
void Exc()
{
init(ni, mi, Ui, Vi, Wi);
int q;
cin >> q;
for (int x = 1; x <= q; x++)
{
int a, b;
cin >> a >> b;
cout << getMinimumFuelCapacity(a, b) << "\n";
}
}
int main()
{
freopen("SWAP.INP", "r", stdin);
//freopen("SWAP.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
#endif // cpismylifeOwO