752 . 機關設計

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

66.7% (4/6)

Tags

apcsc apcsc-graph

Description

作為一個軌道機關設計師，你製作了一連串小球下落的軌道。這個軌道有 $N-1$ 個中繼點編號 $1\sim N-1$ 以及 $N$ 個終點編號 $N\sim 2N-1$，其中編號 $1$ 的中繼點是小球進入的起點。這個機關每個中繼點都連接左右兩個出口，出口可能連接其他中繼點或終點。而終點便是囤積小球的地方，所有先前抵達的小球都會累積在這。

對於每個中繼點，所有從左側出口能到達的終點所累積的小球重量都會成為左側軌道的負重，同理右側軌道也有負重。每次小球都會選擇負重較輕的那側出口離開，如果一樣重則選擇左邊。現在請你模擬 $M$ 個小球依序落下的過程，並回答這 $M$ 個小球分別落入哪個終點。在開始之前，終點可能已累積了一些小球。

Input Format

輸入第一行是兩個整數 $N, M$，分別代表軌道終點數量和要模擬的小球數量。
輸入第二行是 $N$ 個整數 $w_N, w_{N+1}, \dots, w_{2N-1}$，分別代表編號 $N, N+1, \dots, 2N-1$ 終點的初始重量。
輸入第三行是 $M$ 個整數 $b_1, b_2, \dots, b_M$，代表依序進入軌道的小球重量。
接著有 $N-1$ 行，每行有三個數字 $p, s, t$，代表編號 $p$ 的中繼點連接 $s, t$ 兩個出口。
所有數字皆以空白分隔。

輸入保證 $1\le N\le 10^ 5$，$1\le M\le 100$，所有初始重量加上小球重量不超過 $10^ 9$，且一定是合法軌道，軌道連通且小球下落一定會結束在某個終點。

Output Format

輸出一行 $M$ 個空白分隔的整數，代表小球抵達哪個終點。

Sample Input 1

4 4
5 2 6 0
1 7 6 4
1 3 2
3 4 6
2 5 7

Sample Output 1

7 7 5 4

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
Submit
Back to Top