Fertilizing Pastures
다이아몬드 V의견: 0
There are \(N\) pastures (\(2 \le N \le 2\cdot 10^5\)), connected by \(N-1\) roads,
such that they form a tree. Every road takes 1 second to cross. Each pasture
starts out with 0 grass, and the \(i\)th pasture's grass grows at a rate of \(a_i\)
(\(1\le a_i\le 10^8\)) units per second. Farmer John is in pasture 1 at the
start, and needs to drive around and fertilize the grass in every pasture. If
he visits a pasture with \(x\) units of grass, it will need \(x\) amount of
fertilizer. A pasture only needs to be fertilized the first time it is visited,
and fertilizing a pasture takes 0 time.
The input contains an additional parameter \(T\in \{0,1\}\).
- If \(T=0\), Farmer John must end at pasture 1.
- If \(T=1\), Farmer John may end at any pasture.
Compute the minimum amount of time it will take to fertilize every pasture and
the minimum amount of fertilizer needed to finish in that amount of time.
Problem credits: Rohin Garg
SCORING
- Inputs 3-10: \(T=0\)
- Inputs 11-22: \(T=1\)
- Inputs 3-6 and 11-14: No pasture is adjacent to more than three roads.
Problem credits: Rohin Garg
The first line contains \(N\) and \(T\).
Then for each \(i\) from \(2\) to \(N\), there is a line containing \(p_i\) and \(a_i\),
meaning that there is a road connecting pastures \(p_i\) and \(i\). It is guaranteed
that \(1\le p_i
The minimum amount of time and the minimum amount of fertilizer, separated by
spaces.
5 0
1 1
1 2
3 1
3 48 21The optimal route for Farmer John is as follows:
- At time \(1\), move to node \(3\), which now has \(1 \cdot 2 = 2\) grass and so needs \(2\) fertilizer.
- At time \(2\), move to node \(5\), which now has \(2 \cdot 4 = 8\) grass and so needs \(8\) fertilizer.
- At time \(3\), move back to node \(3\), which we already fertilized and so don't need to fertilize again.
- At time \(4\), move to node \(4\), which now has \(4 \cdot 1 = 4\) grass and so needs \(4\) fertilizer.
- At time \(5\), move back to node \(3\), which we already fertilized.
- At time \(6\), move back to node \(1\).
- At time \(7\), move to node \(2\), which now has \(7 \cdot 1 = 7\) grass and so needs \(7\) fertilizer.
- At time \(8\), return to node \(1\).
This route takes \(8\) time and uses \(2 + 8 + 4 + 7 = 21\) fertilizer. It can be
shown that \(8\) is the least possible amount of time for any route that returns
to node \(1\) at the end and \(21\) is the least possible fertilizer used for any
route that returns to node \(1\) and takes \(8\) time.
5 1
1 1
1 2
3 1
3 46 29The optimal route for Farmer John is as follows:
- At time \(1\), move to node \(2\), which now has \(1 \cdot 1 = 1\) grass and so needs \(1\) fertilizer.
- At time \(2\), move back to node \(1\).
- At time \(3\), move to node \(3\), which now has \(3 \cdot 2 = 6\) grass and so needs \(6\) fertilizer.
- At time \(4\), move to node \(5\), which now has \(4 \cdot 4 = 16\) grass and so needs \(16\) fertilizer.
- At time \(5\), move back to node \(3\), which we already fertilized and so don't need to fertilize again.
- At time \(6\), move to node \(4\), which now has \(6 \cdot 1 = 6\) grass and so needs \(6\) fertilizer.
This route takes \(6\) time and uses \(1 + 6 + 16 + 6 = 29\) fertilizer. It can be
shown that \(6\) is the least possible amount of time for any route and \(29\) is
the least possible fertilizer used for any route that takes \(6\) time.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold
평가 및 의견
Fertilizing Pastures
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Fertilizing Pastures