Tractor Paths
다이아몬드 IV의견: 0
Note: The time limit for this problem is 4s, twice the default. The memory
limit for this problem is 512MB, twice the default.
Farmer John has \(N\) (\(2\le N\le 2\cdot 10^5\)) tractors, where the \(i\)th tractor
can only be used within the inclusive interval \([\ell_i,r_i]\). The tractor intervals
have left endpoints \(\ell_1<\ell_2<\dots<\ell_N\) and right endpoints \(r_1
Some of the tractors are special.
Two tractors \(i\) and \(j\) are said to be adjacent if \([\ell_i,r_i]\) and
\([\ell_j,r_j]\) intersect. Farmer John can transfer from one tractor to any adjacent tractor.
A path between two tractors \(a\) and \(b\)
consists of a sequence of transfers such that the first tractor in the sequence
is \(a\), the last tractor in the sequence is \(b\), and every two consecutive
tractors in the sequence are adjacent. It is guaranteed that there is a path
between tractor \(1\) and tractor \(N\). The length of a path is the number of
transfers (or equivalently, the number of tractors within it minus one).
You are given \(Q\) (\(1\le Q\le 2\cdot 10^5\)) queries, each specifying a pair of
tractors \(a\) and \(b\) (\(1\le a
- The length of any shortest path between tractor \(a\) to tractor \(b\).
- The number of special tractors such that there exists at least one shortest path from tractor \(a\) to tractor \(b\) containing it.
Problem credits: Benjamin Qi
SCORING
- Inputs 2-3: \(N,Q\le 5000\)
- Inputs 4-7: There are at most 10 special tractors.
- Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(Q\).
The next line contains a string of length \(2N\) consisting of Ls and Rs,
representing the left and right endpoints in sorted order. It is guaranteed that
for each proper prefix of this string, the number of Ls exceeds the number of
Rs.
The next line contains a bit string of length \(N\), representing for each
tractor whether it is special or not.
The next \(Q\) lines each contain two integers \(a\) and \(b\), specifying a query.
For each query, the two quantities separated by spaces.
8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 51 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2The \(8\) tractor intervals, in order, are
\([1, 5], [2, 10], [3, 11], [4, 12], [6, 13], [7, 14], [8, 15], [9, 16]\).
For the \(4\)th query, there are three shortest paths between the \(1\)st and \(5\)th
tractor: \(1\) to \(2\) to \(5\), \(1\) to \(3\) to \(5\), and \(1\) to \(4\) to \(5\). These
shortest paths all have length \(2\).
Additionally, every tractor \(1,2,3,4,5\) is part of one of the three shortest
paths mentioned earlier, and since \(1,2,4,5\) are special, there are \(4\) special
tractors such that there exists at least one shortest path from tractor \(1\) to
\(5\) containing it.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Platinum
평가 및 의견
Tractor Paths
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tractor Paths