P9466 [EGOI 2023] Bikes vs Cars / Bicycles and Cars

Day 1 Problem D. Translated from [EGOI2023 bikesvscars](https://egoi23.se/assets/tasks/day1/bikesvscars.pdf). [](https://creativecommons.org/licenses/by-sa/3.0/)

In Lund, cycling is a common way to get around, but sometimes narrow streets make it hard for cars and bicycles to pass. To improve this situation, the local government wants to completely redesign the city’s street network. There are $N$ key locations in Lund (numbered from $0$ to $N-1$), and people often travel between them. People travel between two locations along a path, where a path is a sequence of streets from one location to the other. A vehicle (car or bicycle) can travel along a path if and only if all streets on the path are at least as wide as the vehicle. Each newly built street connects two key locations and has total width $W$. This width can be split in any way into a bicycle lane and a car lane. In Lund, some engineers have recently invented cars and bicycles of width $0$ (they can travel on roads of width $0$). These engineers measured the widths of cars and bicycles in the city. For every pair of key locations, they know the width of the widest car and the widest bicycle that can travel between them, and the government also requires that wider cars and bicycles must not be able to travel between them. Formally, for any $i,j$ ($0\le i < j\le N-1$), you are given two integers $C_{i,j}$ and $B_{i,j}$. Your task is to construct a street network connecting these $N$ locations. All streets have total width $W$, but for any street $s$, you may choose its bicycle-lane width $b_s$ and car-lane width $W-b_s$. The network must satisfy: - It must be possible to travel between any two locations. This may require a bicycle or car of width $0$. - For each pair of locations $i,j$ (where $i

The first line contains two integers $N,W$, the number of key locations and the street width. The next $N-1$ lines contain $C_{i,j}$. The $j$-th of these lines contains all $C_{i,j}$ with $i

If no street network satisfying the requirements exists, output `NO`. Otherwise, output an integer $M$ on the first line, the number of streets you build. Then output $M$ lines, each containing three integers $u,v,b$, describing a street between $u$ and $v$ whose bicycle-lane width is $b$ (and car-lane width is $W-b$). You may use at most $2023$ streets. The streets you output must satisfy $0\le b\le W$, $0\le u,v\le N-1$, and $u\ne v$. You may use multiple streets between the same pair of key locations (possibly with different bicycle-lane widths). If there are multiple solutions, you may output any one.

**Explanation of Sample 1** In sample $1$, the street width is $1$. We need a bicycle lane of width at least $1$ and a car lane of width at least $1$ between $0$ and $1$. The solution is to connect them with two separate streets: one with bicycle-lane width $1$, and the other with car-lane width $1$.  --- **Explanation of Sample 2** In sample $2$, the street width is still $1$. We need a bicycle lane of width $1$ connecting every pair of key locations, and a car lane of width $1$ connecting $1,2$ and $2,3$. This contradicts $C_{1,3}=0$: there should not be a car-lane path of width $1$ from $1$ to $3$, but we could combine the two paths mentioned above to form such a path. Therefore, it is impossible to construct a street network that satisfies the requirements. --- **Explanation of Sample 3** In sample $3$, the street network in the figure satisfies all requirements. For example, there should be a car-lane path of width $1=C_{0,5}$ between $0$ and $5$ (path $0\to 2\to 4\to 5$), and a bicycle-lane path of width $3=B_{0,5}$ between $0$ and $5$ (path $0\to 3\to 4\to 5$). Also, one can verify that there is no path with a larger minimum width. Note that sample $3$ may have many other valid solutions.  --- **Constraints** For all testdata, $2\le N\le 500$, $1\le W\le 10^6$, $0\le C_{i,j},B_{i,j}\le W$. - Subtask 1 ($10$ points): all $C_{i,j}$ are equal, all $B_{i,j}$ are equal, $N\le 40$. - Subtask 2 ($5$ points): all $C_{i,j}$ are equal, all $B_{i,j}$ are equal. - Subtask 3 ($17$ points): $N\le 40$. - Subtask 4 ($18$ points): $W=1$. - Subtask 5 ($19$ points): all $B_{i,j}$ are equal. - Subtask 6 ($31$ points): no special constraints. Translated by ChatGPT 5