| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1092899 | raphaelp | Swapping Cities (APIO20_swap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #include "swap.h"
#include <bits/stdc++.h>
using namespace std;
class UnionFind
{
private:
vector<int> p;
public:
UnionFind(int x)
{
p.assign(x, 0);
for (int i = 0; i < x; i++)
p[i] = i;
}
int find(int x) { return (x == p[x]) ? x : p[x] = find(p[x]); }
bool merge(int a, int b)
{
int x = find(a), y = find(b);
if (x == y)
return 0;
p[x] = y;
return 1;
}
};
vector<vector<int>> lca, lca2, lca3;
vector<int> depth;
void dfs(int x, int p, vector<vector<pair<int, int>>> &AR, vector<int> &best, int prof)
{
depth[x] = prof;
lca[0][x] = p;
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
lca3[0][AR[x][i].first] = AR[x][i].second;
dfs(AR[x][i].first, x, AR, best, prof + 1);
best[x] = min(best[x], max(best[AR[x][i].first], AR[x][i].second));
}
}
void dfs2(int x, int p, vector<vector<pair<int, int>>> &AR, vector<int> &best)
{
lca2[0][x] = min(best[x], best[p]);
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
best[AR[x][i].first] = min(best[AR[x][i].first], max(best[x], AR[x][i].second));
dfs2(AR[x][i].first, x, AR, best);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
vector<vector<int>> Tab;
vector<vector<pair<int, int>>> AR2(N);
for (int i = 0; i < M; i++)
{
Tab.push_back({W[i], U[i], V[i]});
AR2[U[i]].push_back({W[i], V[i]});
AR2[V[i]].push_back({W[i], U[i]});
}
for (int i = 0; i < N; i++)
sort(AR2[i].begin(), AR2[i].end());
sort(Tab.begin(), Tab.end());
UnionFind UF(N);
vector<vector<pair<int, int>>> AR(N);
vector<int> best(N, 1000000010);
for (int i = 0; i < M; i++)
{
if (UF.merge(Tab[i][1], Tab[i][2]))
{
AR[Tab[i][1]].push_back({Tab[i][2], Tab[i][0]});
AR[Tab[i][2]].push_back({Tab[i][1], Tab[i][0]});
}
else
{
best[Tab[i][1]] = min(best[Tab[i][1]], Tab[i][0]);
best[Tab[i][2]] = min(best[Tab[i][2]], Tab[i][0]);
}
}
for (int i = 0; i < N; i++)
{
if (AR2[i].size() >= 3)
{
best[i] = min(best[i], max(AR2[i][0].first, max(AR2[i][1].first, AR2[i][2].first)));
}
}
lca.assign(log2(N) + 1, vector<int>(N, 0));
lca2.assign(log2(N) + 1, vector<int>(N, 0));
lca3.assign(log2(N) + 1, vector<int>(N, 0));
depth.assign(N, 0);
dfs(0, 0, AR, best, 0);
dfs2(0, 0, AR, best);
for (int i = 1; i <= log2(N); i++)
{
for (int j = 0; j < N; j++)
{
lca[i][j] = lca[i - 1][lca[i - 1][j]];
lca2[i][j] = min(lca2[i - 1][j], lca2[i - 1][lca[i - 1][j]]);
lca3[i][j] = max(lca3[i - 1][j], lca3[i - 1][lca[i - 1][j]]);
}
}
}
int getMinimumFuelCapacity(int X, int Y)
{
int a = X, b = Y, N = lca[0].size();
int best = 1000000010;
int cost = 0;
if (depth[a] > depth[b])
swap(a, b);
for (int i = log2(N); i >= 0; i--)
{
if (depth[lca[i][b]] >= depth[a])
{
best = min(best, lca2[i][b]);
cost = max(cost, lca3[i][b]);
b = lca[i][b];
}
}
if (a == b)
return max(best, cost);
for (int i = log2(N); i >= 0; i--)
{
if (lca[i][a] != lca[i][b])
{
best = min(best, min(lca2[i][a], lca2[i][b]));
cost = max(cost, max(lca3[i][a], lca3[i][b]));
a = lca[i][a];
b = lca[i][b];
}
}
best = min(best, min(lca2[0][a], lca2[0][b]));
cost = max(cost, max(lca3[0][a], lca3[0][b]));
return max(best, cost);
}
int main()
{
int N, M;
cin >> N >> M;
vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; i++)
{
cin >> U[i] >> V[i] >> W[i];
}
init(N, M, U, V, W);
int Q;
cin >> Q;
for (int i = 0; i < Q; i++)
{
int a, b;
cin >> a >> b;
cout << getMinimumFuelCapacity(a, b) << '\n';
}
}