레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 1.5배인 3초이다.*
농부 존의 농장 구조는 \(N\)개의 정점과 \(M\)개의 가중치 없는 간선으로 이루어진 연결된 무방향 그래프로 나타낼 수 있다 (\(2 \leq N \leq 2 \cdot 10^5, N - 1 \leq M \leq 2 \cdot 10^5\)). 처음에 농부 존은 농장 \(1\)로 표현되는 그의 헛간에 있다.
처음에 농장 \(s_1, s_2, \ldots, s_K\)에는 꽃밭이 있고 농장 \(d_1, d_2, \ldots, d_L\)은 목적지 농장이다. 농부 존은 다음을 만족하는 경로를 예쁘다고 부른다.
- 농장 \(1\)에서 시작한다.
- 어떤 목적지 농장 \(x\)에서 끝난다.
- 농장 \(1\)에서 시작하여 농장 \(x\)에서 끝나는 더 짧은 경로가 존재하지 않는다.
- 농부 존이 경로를 따라가며 모든 꽃밭을 방문한다.
농부 존은 마법 지팡이를 휘둘러 최대 한 개의 농장에 (꽃밭이 아직 없다면) 꽃밭을 추가로 만들 수 있다. 하지만 농부 존은 결단력이 부족하다. \(2\)번부터 \(N\)번까지의 각 농장 \(f\)에 대해, 농부 존이 일시적으로 농장 \(f\)에 꽃밭을 만들었을 때 예쁜 경로가 존재하는지 판별하시오.
테스트 케이스가 여러 개 있으며, 각 케이스는 독립적으로 처리해야 한다는 점에 유의하라.
문제 제공: Chongtian Ma
채점 방식
- 입력 4-6: \(K = 0\)이고 \(L = 1\)
- 입력 7-9: \(K = 0\)
- 입력 10-23: 추가 제약 조건이 없다.
문제 제공: Chongtian Ma
첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1 \leq T \leq 100\))가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\), \(M\), \(K\), \(L\) (\(0 \leq K \leq N - 1, 1 \leq L \leq N - 1\))이 주어진다.
다음 줄에 \(s_1, s_2, \ldots, s_K\) (\(2 \leq s_i \leq N\), \(s_i\)는 모두 서로 다름)가 주어진다.
다음 줄에 \(d_1, d_2, \ldots, d_L\) (\(2 \leq d_i \leq N\), \(d_i\)는 모두 서로 다름)이 주어진다.
다음 \(M\)개의 줄에 \(u\)와 \(v\)가 주어지며, 이는 농장 \(u\)와 \(v\) 사이에 무방향 간선이 있음을 나타낸다. 모든 간선의 길이는 같다고 간주한다. 다중 간선이나 자기 루프는 없음이 보장된다.
모든 테스트 케이스에 대한 \(N\)의 합과 \(M\)의 합 모두 \(10^6\)을 넘지 않음이 보장된다.
각 테스트 케이스마다 길이 \(N - 1\)의 이진 문자열을 출력한다. 문자열의 \(i\)번째 문자는 \((i+1)\)번째 농장에 대한 답이 참이면 \(1\)이어야 한다.
1
7 7 0 1
5
1 2
2 3
3 4
4 5
5 6
6 7
3 6111110Since \(5\) is the only destination farm, the answer holds true if the \(i\)'th farm
lies on any shortest path from \(1\) to \(5\).
There are two shortest paths from \(1\) to \(5\), which are
$1 \rightarrow 2 \rightarrow
3 \rightarrow 4 \rightarrow 5$ and
$1 \rightarrow 2 \rightarrow
3 \rightarrow 6 \rightarrow 5$.
Since there are no farms that already contain flower fields, the answer for farm
\(i\) holds true if farm \(i\) lies on at least one of the two aforementioned paths.
1
6 6 0 2
5 3
1 2
2 3
3 4
4 5
5 6
2 511010There are two destination farms: \(5\) and \(3\). Since there are no farms that
already contain flower fields, the \(i\)'th farm must lie on a shortest path to
either \(5\) or \(3\). Since farm \(2\) lies on a shortest path to farm \(5\), so the
answer holds for farm \(2\). Trivially, farm \(3\) lies on the shortest path to farm
\(3\) and farm \(5\) lies on the shortest path to farm \(5\).
3
4 3 2 1
2 3
4
1 2
2 3
3 4
4 4 2 1
2 3
4
1 2
1 3
2 4
3 4
5 5 2 1
2 4
5
1 2
1 3
2 4
3 4
4 5111
000
1011For the first test case, the answer holds true for the \(i\)'th farm if FJ can
pass through farm \(i\), farm \(2\), and farm \(3\) (in no particular order) on some
shortest path to farm \(4\). It can be shown that the answer holds true for all
farms.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Gold