1802 . 最短路徑

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

baluteshih

User's AC Ratio

37.5% (3/8)

Submission's AC Ratio

31.6% (18/57)

Tags

POI XIX-POI-3rd

Description

http://main.edu.pl/en/archive/oi/19/pen
現在A公司中有N個員工，編號為1到N，其中包含一個CEO。由於A公司的階級制度十分嚴謹，除了CEO以外，每個員工都有恰一個老闆，而一個人的老闆、老闆的老闆、……，全部統稱為這個員工的「老闆們」。
這個公司有三個規定：
1. 每個員工的薪水都要介於1到N之間，且兩兩不相同。
2. 每個員工的薪水都比他老闆們的薪水低。
3. 階級高於一定程度的員工必須公布他的薪水。具體來說，如果一個員工的薪水有被公布，那麼他「老闆們」的薪水全部都要被公布。

你任職於和A公司競爭的B公司，因此你藉由這些被公布的員工薪水，推論出那些沒被公布的員工的薪水。但是因為A公司組織龐大，所以你要寫一個程式來執行這項任務。

Input Format

輸入第一行包含一個正整數$N\leq 10^ 6$，代表A公司員工人數。
接下來有N行，每行有兩個非負整數$p_i, z_i$，分別代表編號為$i$的員工的老闆編號和他的薪水。如果$p_i=i$，代表他是CEO；如果$z_i=0$，代表他的薪水沒有被公布。

Output Format

輸出N行，每一行有一個正整數。如果編號i的員工薪水被公布，或者沒被公布但是可以推論知道他的薪水，請在第i行輸出他的薪水。否則，在第i行輸出一個0。

Sample Input 1

10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

Sample Output 1

2
10
1
9
5
8
0
0
0
0

Hints

Problem Source

POI XIX Stage 3
Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 6
2 1~6 6
3 7~12 6
4 13~15 6
5 16~18 6
6 19~21 6
7 22 6
8 23 6
9 24 6
10 25 6
11 26 6
12 27 6
13 28 6
14 29 7
15 30 7
16 31 7
17 32 7

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 2
2 1000 131072 262144 2
3 1000 131072 262144 2
4 1000 131072 262144 2
5 1000 131072 262144 2
6 1000 131072 262144 2
7 1000 131072 262144 3
8 1000 131072 262144 3
9 1000 131072 262144 3
10 1000 131072 262144 3
11 1000 131072 262144 3
12 1000 131072 262144 3
13 1000 131072 262144 4
14 1000 131072 262144 4
15 1000 131072 262144 4
16 1000 131072 262144 5
17 1000 131072 262144 5
18 1000 131072 262144 5
19 1000 131072 262144 6
20 1000 131072 262144 6
21 1000 131072 262144 6
22 1000 131072 262144 7
23 1000 131072 262144 8
24 1000 131072 262144 9
25 1000 131072 262144 10
26 1000 131072 262144 11
27 1000 131072 262144 12
28 1000 131072 262144 13
29 1000 131072 262144 14
30 1000 131072 262144 15
31 1000 131072 262144 16
32 1000 131072 262144 17
Submit
Back to Top