# APIO 2020 Problems and Solutions – Swapping Cities ## Problem :

There are `NN` cities in Indonesia, numbered from `00 to N - 1N−1`. There are also `MM` two-way roads, numbered from `00 to M - 1M−1`. Each road connects two different cities. The `ii-th` road connects the `U[i]U[i]-th` city and the `V[i]V[i]-th` city and consumes `W[i]W[i]` units of gas when traversed by car. The cities are connected such that it is possible to travel between any pair of cities through the roads.

For each of the next `QQ` days, a pair of cities would like to establish a political relationship. In particular, on the `jj-th` day, the `X[j]X[j]-th` city would like to establish a political relationship with the `Y[j]Y[j]-th `city. In order to do this, the `X[j]X[j]-th` city should send a representative to go to the `Y[j]Y[j]`-th city by car. Similarly, the `Y[j]Y[j]-th` city should also send a representative to go to the `X[j]X[j]-th` city by car.

To avoid congestion, both cars should not meet at any point in time. In particular, both cars should not be in the same city at the same time. Also, both cars should not traverse the same road in the opposite direction at the same time. Additionally, cars that traverse the road must complete the road and go to the destination city (in other words, cars are not allowed to make a U-turn in the middle of a road). However, cars are allowed to visit the same city and road more than once. In addition, cars may also wait at any city at any point in time.

Since cars with high fuel capacity are expensive, both cities would like to choose routes for both cars such that the maximum fuel capacity of the two cars is minimized. There are gas stations in each city with an infinite supply of gas, thus the fuel capacity required by a car is the maximum gas consumption among all roads traversed by the car.

You have to implement `init` and `getMinimumFuelCapacity` functions.

• `init(N, M, U, V, W)` – This function will be called by the grader exactly once before any `getMinimumFuelCapacity` calls.
• `NN`: An integer representing the number of cities.
• `MM`: An integer representing the number of roads.
• `UU:` An array of `MM` integers representing the first endpoint of the roads.
• `VV:` An array of `MM` integers representing the second endpoint of the roads.
• `WW`: An array of `MM` integers representing the gas consumption of the roads.
• `getMinimumFuelCapacity(X, Y)` – This function will be called by the grader exactly `QQ` times.
• `XX`: An integer representing the first city.
• `YY`: An integer representing the second city.
• This function must return an integer representing the minimum unit of fuel capacity of the maximum fuel capacity of the two cars such that a representative from the `XX-th` city can go to the `YY-th` city and a representative from the `YY-th` city can go to the `XX-th` city following the rules explained in the problem statement, or `-1−1` if it is impossible to do so.

### Example :

In the first example, `N = 5N=5, M = 6M=6, U = [0, 0, 1, 1, 1, 2]U=[0,0,1,1,1,2], V = [1, 2, 2, 3, 4, 3]V=[1,2,2,3,4,3], W = [4, 4, 1, 2, 10, 3]W=[4,4,1,2,10,3], Q = 3Q=3, X = [1, 2, 0]X=[1,2,0], Y = [2, 4, 1]Y=[2,4,1]`. The example is illustrated by the following image:

The grader will initially call `init(5, 6, [0, 0, 1, 1, 1, 2], [1, 2, 2, 3, 4, 3], [4, 4, 1, 2, 10, 3])`. After that, the grader will call the following:

• `getMinimumFuelCapacity(1, 2)`. First, the car from the first city can go to the third city. Next, the car from the second city can go to the first city, and the car from the third city can go to the second city. Therefore, the maximum fuel capacity of the two cars is 33 units of fuel (required to go from the third city to the second city. There is no route that requires less fuel capacity, thus the function should return 33.
• `getMinimumFuelCapacity(2, 4)`. Any car that goes to or from the fourth city should require 1010 units of fuel capacity, thus the function should return 1010.
• `getMinimumFuelCapacity(0, 1)`. The function should return 44.

In the second example, `N = 3N=3, M = 2M=2, U = [0, 0]U=[0,0], V = [1, 2]V=[1,2], W = [5, 5]W=[5,5], Q = 1Q=1, X = X=, Y = Y=`. The example is illustrated by the following image:

The grader will initially call `init(3, 2, [0, 0], [1, 2], [5, 5])`. After that, the grader will call the following:

• `getMinimumFuelCapacity(1, 2)`. It is impossible for the car in the first city to go to the second city without meeting the other car at some time, thus the function should return `-1−1`.

### Constraints :

• `2 \le N \le 100\,0002≤N≤100000.`
• `N - 1 \le M \le 200\,000N−1≤M≤200000.`
• `0 \le U[i] \lt V[i] \lt N0≤U[i]<V[i]<N.`
• `There is at most one road between each pair of cities.`
• `It is possible to travel between any pair of cities through the roads.`
• `1 \le W[i] \le 10^91≤W[i]≤109.`
• `1 \le Q \le 200\,0001≤Q≤200000.`
• `0 \le X[j] \lt Y[j] \lt N0≤X[j]<Y[j]<N.`

### Subtask 1 (6 points) :

• Each city is an endpoint of at most two roads.

### Subtask 2 (7 points) :

• `M = N - 1M=N−1.`
• `U[i] = 0U[i]=0.`

### Subtask 3 (17 points) :

• `Q \le 5Q≤5.`
• `N \le 1\,000N≤1000.`
• `M \le 2\,000M≤2000.`

### Subtask 4 (20 points) :

• `Q \le 5Q≤5.`

### Subtask 5 (23 points) :

• `M = N - 1M=N−1.`

### Subtask 6 (27 points) :

``````N M
U V W
U V W
.
.
.
U[M-1] V[M-1] W[M-1]
Q
X Y
X Y
.
.
.
X[Q-1] Y[Q-1]
``````

For each `getMinimumFuelCapacity` call, the sample grader prints the value returned by the function.

## Solution :

``````#include "swap.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
const int mod = 1e9 + 7;

struct disj{
struct node{
int pa, max_deg, cycle, updated;
bool operator<(const node &n)const{
return updated < n.updated;
}
};
// persistent
vector<node> nodes[MAXN];

// only used in creation
vector<int> memb[MAXN];
int deg[MAXN];
void init(int n){
for(int i=0; i<n; i++){
memb[i].push_back(i);
nodes[i].push_back({i, 0, 0, -1});
}
}
int find(int x){
return nodes[x].back().pa;
}
void add_edge(int x, int y, int i){
deg[x]++; deg[y]++;
int new_deg = max(deg[x], deg[y]);
x = find(x); y = find(y);
if(x != y){
if(sz(memb[x]) < sz(memb[y])) swap(x, y);
for(auto &v : memb[y]){
node prv = nodes[v].back();
prv.pa = x;
prv.updated = i;
nodes[v].push_back(prv);
memb[x].push_back(v);
}
node prv = nodes[x].back();
prv.max_deg = max(prv.max_deg, nodes[y].back().max_deg);
prv.cycle |= nodes[y].back().cycle;
prv.updated = i;
nodes[x].push_back(prv);
memb[y].clear();
}
node prv = nodes[x].back();
if(x == y) prv.cycle = 1;
prv.max_deg = max(prv.max_deg, new_deg);
prv.updated = i;
nodes[x].push_back(prv);
}
node get_node(int x, int t){
return *--upper_bound(all(nodes[x]), (node){-1, -1, 0, t});
}
}disj;

bool isGood(int u, int v, int m){
auto gnx = disj.get_node(u, m);
auto gny = disj.get_node(v, m);
if(gnx.pa != gny.pa) return 0;
auto val = disj.get_node(gnx.pa, m);
return val.max_deg >= 3 || val.cycle;
}

int n, m;

struct edg{
int s, e, x;
}a[MAXN];

void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
disj.init(n);
for(int i=0; i<M; i++) a[i] = {U[i], V[i], W[i]};
sort(a, a + M, [&](const edg &a, const edg &b){
return a.x < b.x;
});
for(int i=0; i<M; i++) disj.add_edge(a[i].s, a[i].e, i);
}

int getMinimumFuelCapacity(int X, int Y) {
int s = 0, e = m;
while(s != e){
int m = (s + e) / 2;
if(isGood(X, Y, m)) e = m;
else s = m + 1;
}
if(s == m) return -1;
return a[s].x;
}``````

50 total views,  7 views today

#### Post Disclaimer

the above hole problem statement is given by apio2020.id but the solution is generated by the SLTECHACADEMY authority if any of the query regarding this post or website fill the following contact form thank you