레이팅 미적용참고: 이 문제의 시간 제한은 기본의 두 배인 4초이다. 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.
농부 존은 \(N\) (\(2\le N\le 2\cdot 10^5\))대의 트랙터를 가지고 있고, \(i\)번째 트랙터는 양 끝점을 포함하는 구간 \([\ell_i,r_i]\) 안에서만 사용할 수 있다. 트랙터 구간의 왼쪽 끝점은 \(\ell_1<\ell_2<\dots<\ell_N\)이고 오른쪽 끝점은 \(r_1
두 트랙터 \(i\)와 \(j\)는 \([\ell_i,r_i]\)와 \([\ell_j,r_j]\)가 교차하면 인접하다고 한다. 농부 존은 한 트랙터에서 인접한 아무 트랙터로 옮겨 탈 수 있다. 두 트랙터 \(a\)와 \(b\) 사이의 경로는 옮겨 타기의 수열로 이루어지며, 수열의 첫 트랙터는 \(a\)이고 마지막 트랙터는 \(b\)이며 수열에서 연속한 두 트랙터는 항상 인접하다. 트랙터 \(1\)과 트랙터 \(N\) 사이에 경로가 존재함이 보장된다. 경로의 길이는 옮겨 탄 횟수(즉, 경로에 포함된 트랙터 수에서 하나를 뺀 값)이다.
\(Q\) (\(1\le Q\le 2\cdot 10^5\))개의 쿼리가 주어지며, 각 쿼리는 트랙터 쌍 \(a\)와 \(b\) (\(1\le a
- 트랙터 \(a\)에서 트랙터 \(b\)까지의 최단 경로의 길이.
- 트랙터 \(a\)에서 트랙터 \(b\)까지의 최단 경로 중 그 트랙터를 포함하는 것이 적어도 하나 존재하는 특별한 트랙터의 수.
출제자: Benjamin Qi
배점
- 입력 2-3: \(N,Q\le 5000\)
- 입력 4-7: 특별한 트랙터는 최대 10대이다.
- 입력 8-16: 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 줄에 L과 R로 이루어진 길이 \(2N\)의 문자열이 주어지는데, 이는 왼쪽 끝점과 오른쪽 끝점을 정렬된 순서로 나타낸 것이다. 이 문자열의 모든 진 접두사(proper prefix)에서 L의 개수가 R의 개수보다 많음이 보장된다.
다음 줄에 길이 \(N\)의 비트 문자열이 주어지며, 각 트랙터가 특별한지 여부를 나타낸다.
다음 \(Q\)개의 줄에 각각 쿼리를 지정하는 두 정수 \(a\)와 \(b\)가 주어진다.
각 쿼리에 대해 두 값을 공백으로 구분하여 출력한다.
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