Picking Flowers
골드 II의견: 0
*Note: The time limit for this problem is 3s, 1.5x the default.*
Farmer John's farm structure can be represented as a connected undirected graph
with \(N\) vertices and \(M\) unweighted edges
(\(2 \leq N \leq 2 \cdot 10^5, N - 1 \leq M \leq 2 \cdot 10^5\)). Initially,
Farmer John is at his barn, represented by farm \(1\).
Initially, farms \(s_1, s_2, \ldots, s_K\) contain flower fields and farms
\(d_1, d_2, \ldots, d_L\) are destination farms. FJ calls a path pretty if:
- It starts at farm \(1\).
- It ends at some destination farm \(x\).
- There is no shorter path starting at farm \(1\) and ending at farm \(x\).
- FJ visits all flower fields along the way.
FJ can wave his magic wand and make up to one more farm contain a flower field (if it
doesn't already). However, FJ isn't very decisive. For farms \(f\) numbered \(2\)
through \(N\), after FJ temporarily makes farm \(f\) contain a flower field,
determine if there exists a pretty path.
Note that there are multiple test cases, and each case must be treated
independently.
Problem credits: Chongtian Ma
SCORING
- Inputs 4-6: \(K = 0\) and \(L = 1\)
- Inputs 7-9: \(K = 0\)
- Inputs 10-23: No additional constraints
Problem credits: Chongtian Ma
The first line contains \(T\) (\(1 \leq T \leq 100\)), the number of independent
test cases.
The first line of each test case contains \(N\), \(M\), \(K\), and \(L\)
(\(0 \leq K \leq N - 1, 1 \leq L \leq N - 1\)).
The following line contains \(s_1, s_2, \ldots, s_K\) (\(2 \leq s_i \leq N\), \(s_i\)
are all distinct).
The following line contains \(d_1, d_2, \ldots, d_L\) (\(2 \leq d_i \leq N\), \(d_i\)
are all distinct).
The following \(M\) lines contain \(u\) and \(v\), denoting there is an undirected
edge between farms \(u\) and \(v\). All edges are considered to have equal length.
It is guaranteed that there aren't any multi-edges or self loops.
It is guaranteed that both the sum of \(N\) and the sum of \(M\) do not exceed
\(10^6\) over all test cases.
For each test case, output a binary string of length \(N - 1\). The \(i\)'th
character in the string should be \(1\) if the answer holds true for the
\((i+1)\)'th farm.
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
평가 및 의견
Picking Flowers
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Picking Flowers