TopCoder

PCC
MLEMLEMLETLETLETLEWAWAWAWAWA

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

50.0% (2/4)

Tags

Description

本題是 Two Steps 題形,僅限用 C++ 作答,請詳細閱讀底下實作指示

DanbZisk 在上次的較勁之後,發現他們兩個人都太強了,彼此競爭起來根本沒意義。因此他們決定聯手起來玩最近火紅的遊戲 - 「刂鑳神域」!作為封閉者的 Danb 預先得知了裡面的世界地圖,可以當成是一個有 N 個點和 M 條邊的圖。而他聽說在點 B 有一個會讓強者變無敵的寶劍,因此他決定幫助 Zisk 找到這支劍。

但是事情沒有那麼簡單,Danb 只能在 Zisk 進入遊戲之前跟他單方向傳遞訊息,這個訊息是一個長度不超過 4876301 字串 S。而 Zisk 在進入遊戲時會出現在某個點 A,但是他不知道 A 是什麼,只知道與 A 相鄰的邊所連到的點。由於Zisk 把所有的腦力都拿來記得 S 了,他永遠不會記得之前走過哪些點,或者現在在哪裡。為了成為第一個破關的人,Zisk 希望他能經過最少條邊走到 B

請設計一個 DanbZisk 溝通的方法。Danb 需要從給定的圖和點 B 傳遞訊息 S,而 Zisk 需要根據 A 相鄰的點和 Danb 的訊息找到正確的路。

Instructions

首先,請在程式第一行引入標頭檔 "lib0157.h"

請實作以下三個函式:
std::string Danbing(int N, int M, std::vector<int> U, std::vector<int> V, int B)
N,M 分別是圖的點數跟邊數。U[i],V[i] 是第 i 條邊的兩個端點 0i<MB 是集合地點。
這個函式會回傳一個字串 S,是 DanbZisk 的訊息。

void Ziskinit(std::string S)
這個函式負責把 Danb 訊息傳給 ZiskS 是執行 Danbing 之後所得到的字串。

int Zisking(int N, std::vector<int> adj)
N 是圖的點數。adj 內含 Zisk 所看得到相鄰的點。
這個函式應該回傳一個整數。這個回傳的整數應該是 adj 裡面的某一項 x,代表 Zisk 要前進的點。保證呼叫此函式時,Zisk所在的點不是 B

評測系統進行測試的方法如下:
1. 你的程式會被編譯成兩個分開的執行檔 XY
2. 系統會先執行 X 並且呼叫 Danbing一次,取得 Danb 的字串 S。如果 S 的長度大於 48763,那麼你會獲得一個 WA。
3. 系統開始執行 Y ,並且呼叫 Ziskinit 恰一次。
4. 系統會選擇一些起始點 A1,A2,,Ak。在 Y 依照這些點呼叫 Zisking 若干次。具體來說,對於目前的點 A,如果 Zisking 回傳的結果是 AAB,那麼之後會再依照 A 呼叫 Zisking。如果函式輸出的結果不是走到 B 的最短路徑,你會獲得一個 WA。請注意,系統可以用任意順序呼叫這些起始點,且保證 k5

請勿使用標準輸入輸出 (stdin/stdout) ,如果使用了可能出現不可預測的結果。

Constraints

  • N2023,M48763
  • 保證圖是連通的
  • 保證呼叫 Zisking 時,Zisk所在的點不是 B

Sample Grader

你可以在此處下載 walking.zip,內含五個檔案 walking.cppwalking.hgrader.cppcompile.sh、跟compile.bat。其中 walking.cpp 是你要修改並且上傳的檔案,grader.cpp 是範例評分程式。若要編譯,可以在該目錄內執行 compile.shcompile.bat,這會產生執行檔 walking 。注意,在這裡walking.cpp只會被執行一次,和真正的評分程式不同。

範例評分程式 grader.cpp 用以下格式讀取輸入:

N M
U1 V1
U2 V2
...
UM VM
B
A

評分程式會列印出呼叫 Danbing 之後的字串 S 和長度,以及之後每次呼叫 Zisking 的結果。
如果 Zisking 的回傳結果並不在 adj 內,評分程式會列印 Wrong Answer: Invalid return value 並且結束執行。
如果成功走到 B,那麼評分程式會顯示 Found, distance = 呼叫次數,請注意,評分程式不會檢查該路徑是否最短
如果在N步之內都還沒走到 B,那麼評分程式會顯示 Wrong Answer: Haven't found B after N steps

Input Format

本題沒有輸入

Output Format

本題沒有輸出

Sample Input 1

以下是一組範例輸入:
5 5
1 3
2 4
3 5
3 4
1 2
2
5

Sample Output 1

執行 grader.cpp 時,正確的程式會輸出

Found, distance = 3

Hints

Problem Source

IOICamp 2023 Day1 pS

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~17 無其他限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2