| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 725773 | Cookie | 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<bits/stdc++.h>
using namespace std;
#include "swap.h"
#include <cassert>
#include <cstdio>
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 3e5 + 5;
struct E{
int u, v, w;
bool operator <(const E &b){
return(w < b.w);
}
};
int p[mxn + 1], best[mxn + 1], in[mxn + 1], id = 0, val[mxn + 1], dep[mxn + 1], up[mxn + 1][19];
bool ok[mxn + 1];
vt<int>adj[mxn + 1];
vt<E>edge;
int fp(int u){
if(p[u] == u)return(u);
return(p[u] = fp(p[u]));
}
void unon(int a, int b, int w){
bool valid = (in[a] >= 3 || in[b] >= 3);
a = fp(a); b = fp(b);
valid |= (ok[a] || ok[b]);
int pos = ++id; p[pos] = pos; val[pos] = w;
if(a == b){
// cycle
ok[pos] = 1;
adj[pos].pb(a); p[a] = pos;
return;
}
ok[pos] = valid;
adj[pos].pb(a); adj[pos].pb(b); p[a] = p[b] = pos;
val[pos] = w;
}
void dfs(int s, int mn){
if(ok[s])mn = min(mn, val[s]);
best[s] = mn;
for(auto i: adj[s]){
dep[i] = dep[s] + 1;
up[i][0] = s;
dfs(i, mn);
}
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);
int k = dep[u] - dep[v];
for(int i = 0; i < 19; i++){
if(k & (1 << i)){
u = up[u][i];
}
}
if(u == v)return(u);
for(int i = 18; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[u][i]; v = up[v][i];
}
}
return(up[u][0]);
}
void init(int n, int m, vt<int>u, vt<int>v, vt<int>w){
for(int i = 0; i < m; i++){
edge.pb({u[i], v[i], w[i]});
}
id = n - 1;
sort(edge.begin(), edge.end());
for(int i = 0; i < n; i++){
p[i] = i;
}
for(auto [u, v, w]: edge){
in[u]++; in[v]++;
unon(u, v, w);
}
dfs(id, 1e9 + 1);
for(int i = 1; i < 19; i++){
for(int j = 0; j <= id; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
}
int getMinimumFuelCapacity(int x, int y){
int l = lca(x, y);
if(best[l] == 1e9 + 1)return(-1);
return(best[l]);
}
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;
}