APIO 2020 Problems and Solutions – Swapping Cities

APIO 2020 Problems and Solutions – Swapping Cities
Time limit2 s
Memory limit512 MB

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.

Task :

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 = [1]X=[1], Y = [2]Y=[2]. 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) :

  • No additional constraints.

Sample Grader :

The sample grader reads the input in the following format:

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
.
.
.
U[M-1] V[M-1] W[M-1]
Q
X[0] Y[0]
X[1] Y[1]
.
.
.
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

Leave a Reply

Your email address will not be published. Required fields are marked *