b257: 穿越蟲洞
Tags :
Accepted rate : 3人/7人 ( 43% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-10 10:54

Content
有 N 位運動員 (編為 1 至 N),正在在一條長長的路上進行一項活動。這條路是由一些方格所組成,這些方格順序寫著一些連繼的自然數,即第一格上寫上1,第二格上寫上 2,如此類推。
以下稱這些格為路格。
這條路分成 N 段長度不一定相同的路段,每條路段均有一個起點路格及一個終點路格。
第一段號段的起點格為 1,其終點格為 D1,第二段路段的起點格為 D1+1,其終點格為 D2,第三段號段的起點格為 D2+1,其終點格為 D3,如此類推。

最初,這 N 個運動員按自己的編號順次各自站在自己的起點路格上,然後開始沿著大數字的方向走。

這條路上有 M 個蟲洞,每個蟲洞連接著兩個不同的路格。
當運動員踏進一個蟲洞的一端的路格上時,就會被傳送到蟲洞連接的另一端路格上,而當一個運動員被送到另一端的路格時,他會繼續向大數方向前進,直至他到達其中一個終點為止。
這些蟲洞有以下的特點:
- 蟲洞的兩端分別出現在兩個不同的路段上
- 蟲洞的兩端不會出現在任何起點或終點上
- 任何一個路格最多只會是一個蟲洞的端口
- 蟲洞的端口不會出現在這 N 條路段以外的任何路格上
- 任何蟲洞的組合,均不會構成任何環的出現。換言之,每一位運動員最終必定可以到達其中一個終點

現在我們想知道的是每一個運動員最終會到達哪一個終點。

 

 
 
Input
輸入包括若干組測試數據。每組數據包括有以下格式的一組資料:
- 每組資料的第一行爲兩個正整數 N 和 M,N 表運動員的數目,M 則代表蟲洞的數目 (2 ≤ N ≤ 500,1 ≤ M ≤ 4,000)
- 第二行上有 N 個正整數每一個正整數,這 N 個數順次代表著 N 個終點所在的路格編號。這些編號均小於 109)
- 隨後有 M 行,每行有一對正整數,代表一個蟲洞的兩個端口所在的路格的編號

 輸入的最後一行,有兩個 0,代表輸入的結束。

Output
對應於每一組測試數據,請輸出一行,其上含有 N 個正整數,它們順次代表運動員 1 至 N 所到逹的絡點的路格的編號。
Sample Input #1
3 3
6 10 15
3 9
8 12
14 5
0 0
Sample Output #1
10 6 15
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <10M
不公開 測資點#10 (10%): 1.0s , <10M
Hint :
對於以上的例子,各運動員所走的路線如下:

- 第一位運動員: 1>>3=>9>>10

- 第二位運動員: 7>>8=>12>>14=>5>>6
- 第三位運動員: 11>>12=>8>>9=>3>>5=>14>>15

 其中 "=>" 表示穿越了蟲洞,">>" 表示在正常路上跑。

Tags:
出處:
MOIC2024MCS [管理者:
kulam@g.puic... (林建源)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」