Aoi และ Bitaro เป็นสายลับสังกัดสำนักข่าวสารแห่งชาติของประเทศ JOI ภารกิจครั้งนี้คือการแฝงตัวเข้าไปสืบสวนในประเทศ IOI โดย Bitaro จะแทรกซึมเข้าไปในประเทศ IOI ส่วน Aoi จะออกคำสั่งให้ Bitaro จากประเทศ JOI

ก่อนการแทรกซึม Aoi และ Bitaro ได้รับแผนที่ของประเทศ IOI ประเทศ IOI มีเมือง $N$ เมือง หมายเลขตั้งแต่ $0$ ถึง $N-1$ และมีถนน $M$ สาย หมายเลขตั้งแต่ $0$ ถึง $M-1$ ถนนสายที่ $i$ ($0 \le i \le M-1$) เชื่อมเมือง $A_i$ กับเมือง $B_i$ แบบสองทิศทาง และมีความยาว $C_i$ สามารถเดินทางระหว่างเมืองคู่ใด ๆ ได้โดยผ่านถนนบางสาย Bitaro เดินทางระหว่างเมืองในประเทศ IOI โดยใช้ถนนเหล่านี้

นอกจากนี้ มีแผนการสืบสวน $Q$ แผน แผนที่ $j$ ($0 \le j \le Q-1$) คือการสืบสวนเมือง $T_j$ ในประเทศ IOI

ในตอนแรก ทั้ง Aoi และ Bitaro ได้รับข้อมูลข้างต้นทั้งหมด จากนั้น Bitaro จึงเริ่มแทรกซึมเข้าไปในประเทศ IOI

Bitaro หลบผู้ไล่ล่าจำนวนมาก เอาชนะนักฆ่า และในที่สุดก็แทรกซึมเข้าไปในเมือง $0$ ของประเทศ IOI ได้สำเร็จ อย่างไรก็ตาม เนื่องจากปฏิบัติการแทรกซึมมีความยากลำบากอย่างยิ่ง Bitaro จึงทำข้อมูลบางส่วนเกี่ยวกับประเทศ IOI หายไป โดยเฉพาะข้อมูลความยาวของถนน $K$ สาย ได้แก่ถนน $X_0,X_1,\ldots,X_{K-1}$ กล่าวคือ Bitaro ไม่ทราบค่า $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$ อีกต่อไป โปรดสังเกตว่า แม้ Bitaro จะทำข้อมูลเหล่านี้หาย แต่ Aoi ยังเก็บข้อมูลเหล่านี้ไว้

Bitaro รายงานให้ Aoi ทราบทันทีว่าเขาทำข้อมูลความยาวของถนนสายใดหายไปบ้าง

เพื่อให้ภารกิจสำเร็จ Bitaro ต้องการทราบเส้นทางสั้นที่สุดเส้นทางหนึ่งจากเมือง $0$ ไปยังเมืองเป้าหมายของแต่ละแผนในแผนการสืบสวนทั้ง $Q$ แผน

Aoi จะส่งสตริงที่อักขระแต่ละตัวเป็น 0 หรือ 1 ให้ Bitaro เพื่อช่วยเขา เนื่องจากเสี่ยงต่อการถูกดักฟัง Aoi จึงต้องการให้เนื้อหาที่ส่งให้ Bitaro มีขนาดน้อยที่สุด

จงเขียนโปรแกรมที่ใช้กลยุทธ์ของ Aoi ในการส่งสตริงให้ Bitaro เมื่อได้รับข้อมูลเกี่ยวกับประเทศ IOI แผนการสืบสวน และถนนที่ Bitaro ทำข้อมูลหาย นอกจากนี้ จงเขียนโปรแกรมที่ใช้กลยุทธ์ของ Bitaro ในการหาเส้นทางสั้นที่สุด เมื่อได้รับข้อมูลที่เขามีอยู่และสตริงที่ Aoi ส่งมา

รายละเอียดการเขียนโปรแกรม

คุณต้องส่งไฟล์ 2 ไฟล์

ไฟล์แรกคือ Aoi.cpp ซึ่งใช้กลยุทธ์ของ Aoi และต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้องนำเข้า Aoi.h ด้วยคำสั่งพรีโพรเซสเซอร์ #include

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X)

ฟังก์ชันนี้จะถูกเรียกเพียงครั้งเดียวสำหรับแต่ละกรณีทดสอบ

• พารามิเตอร์ N คือจำนวนเมือง $N$ ในราชอาณาจักร IOI
• พารามิเตอร์ M คือจำนวนถนน $M$ ในราชอาณาจักร IOI
• พารามิเตอร์ Q คือจำนวนแผนการสืบสวน $Q$
• พารามิเตอร์ K คือจำนวนถนนที่ Bitaro ทำข้อมูลความยาวหาย ซึ่งแทนด้วย $K$
• พารามิเตอร์ A, B, C เป็นอาร์เรย์ความยาว $M$ โดยถนนสายที่ $i$ ($0 \le i \le M-1$) เชื่อมเมือง A[i] กับเมือง B[i] แบบสองทิศทาง และมีความยาว C[i]
• พารามิเตอร์ T เป็นอาร์เรย์ความยาว $Q$ โดยแผนที่ $j$ ($0 \le j \le Q-1$) คือการสืบสวนเมือง T[j]
• พารามิเตอร์ X เป็นอาร์เรย์ความยาว $K$ ซึ่งระบุว่า Bitaro ทำข้อมูลความยาวของถนน X[0], X[1], ..., X[K-1] หายไป
• ค่าที่คืนคือสตริง $s$ ที่ Aoi ส่งให้ Bitaro
• อักขระแต่ละตัวของสตริง $s$ ต้องเป็น 0 หรือ 1 หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [1]
• ความยาวของสตริง $s$ ต้องไม่เกิน $12\,000$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [2]

ไฟล์ที่สองคือ Bitaro.cpp ซึ่งใช้กลยุทธ์ของ Bitaro และต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้องนำเข้า Bitaro.h ด้วยคำสั่งพรีโพรเซสเซอร์ #include

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s)

ฟังก์ชันนี้จะถูกเรียกเพียงครั้งเดียว หลังจากเรียกฟังก์ชัน aoi

• พารามิเตอร์ N คือจำนวนเมือง $N$ ในราชอาณาจักร IOI
• พารามิเตอร์ M คือจำนวนถนน $M$ ในราชอาณาจักร IOI
• พารามิเตอร์ Q คือจำนวนแผนการสืบสวน $Q$
• พารามิเตอร์ K คือจำนวนถนนที่ Bitaro ทำข้อมูลความยาวหาย ซึ่งแทนด้วย $K$
• พารามิเตอร์ A, B, C เป็นอาร์เรย์ความยาว $M$ โดยถนนสายที่ $i$ ($0 \le i \le M-1$) เชื่อมเมือง A[i] กับเมือง B[i] แบบสองทิศทาง และมีความยาว C[i]
• พารามิเตอร์ T เป็นอาร์เรย์ความยาว $Q$ โดยแผนที่ $j$ ($0 \le j \le Q-1$) คือการสืบสวนเมือง T[j]
• พารามิเตอร์ X เป็นอาร์เรย์ความยาว $K$ ซึ่งระบุว่า Bitaro ทำข้อมูลความยาวของถนน X[0], X[1], ..., X[K-1] หายไป
• อาร์กิวเมนต์ s เป็นสตริงที่อักขระแต่ละตัวเป็น 0 หรือ 1 และเป็นสตริงที่ Aoi ส่งให้ Bitaro

ภายใน Bitaro.cpp โปรแกรมของคุณสามารถเรียกฟังก์ชันต่อไปนี้ได้

void answer(const std::vector<int> &e)

ในการเรียกฟังก์ชันนี้ครั้งที่ $j+1$ ($0 \le j \le Q-1$) คุณต้องตอบเส้นทางสั้นที่สุดจากเมือง $0$ ไปยังเมือง $T_j$ ซึ่งเป็นเป้าหมายของแผนการสืบสวนที่ $j$

• พารามิเตอร์ e เป็นอาร์เรย์ที่แทนเส้นทางสั้นที่สุดจากเมือง $0$ ไปยังเมือง $T_j$
• ให้ $n$ เป็นความยาวของอาร์เรย์ e สมาชิก e[0], e[1], ..., e[n-1] คือหมายเลขถนนในเส้นทางสั้นที่สุดจากเมือง $0$ ไปยังเมือง $T_j$ ตามลำดับที่ผ่าน
• หากมีเส้นทางสั้นที่สุดได้หลายเส้นทาง สามารถเลือกเส้นทางใดก็ได้เป็นคำตอบ
• สมาชิกแต่ละตัวของพารามิเตอร์ e ต้องมีค่าระหว่าง $0$ ถึง $M-1$ หากไม่เป็นไปตามเงื่อนไขนี้ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [3]

• ลำดับถนนที่อาร์กิวเมนต์ e ระบุต้องเป็นเส้นทางจากเมือง $0$ ไปยังเมือง $T_j$ กล่าวอย่างเป็นทางการคือต้องเป็นไปตามเงื่อนไขต่อไปนี้

  มีลำดับตัวเลข $u_0,u_1,\ldots,u_n$ ที่ทำให้

  • $u_0=0$
  • $u_n=T_j$
  • ถนน e[k] (เมื่อ $0 \le k \le n-1$) เชื่อมเมือง $u_k$ กับเมือง $u_{k+1}$

  หากไม่เป็นไปตามเงื่อนไขเหล่านี้ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [4]

• หากลำดับถนนที่อาร์กิวเมนต์ e ระบุไม่ใช่เส้นทางสั้นที่สุดจากเมือง $0$ ไปยังเมือง $T_j$ เมื่อเทียบกับทุกเส้นทางที่เริ่มจากเมือง $0$ และสิ้นสุดที่เมือง $T_j$ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [5] โดยความยาวของเส้นทางนิยามเป็นผลรวมความยาวของถนนที่ใช้
• ต้องเรียกฟังก์ชัน answer ทั้งหมด $Q$ ครั้งพอดี หากเมื่อฟังก์ชัน bitaro ทำงานจบแล้ว จำนวนครั้งที่เรียกฟังก์ชัน answer ไม่เท่ากับ $Q$ โปรแกรมของคุณจะถูกตัดสินว่า คำตอบผิด [6]

ข้อควรทราบที่สำคัญ

• โปรแกรมของคุณสามารถเขียนฟังก์ชันอื่นสำหรับใช้ภายใน หรือใช้ตัวแปรส่วนกลางได้ ไฟล์ที่ส่งจะถูกคอมไพล์ร่วมกับโปรแกรมตรวจและกลายเป็นไฟล์ปฏิบัติการไฟล์เดียว ตัวแปรส่วนกลางและฟังก์ชันภายในทั้งหมดควรประกาศในเนมสเปซที่ไม่มีชื่อ เพื่อหลีกเลี่ยงการชนกับไฟล์อื่น เมื่อให้คะแนน จะทำงานเป็นสองโพรเซสสำหรับ Aoi และ Bitaro โดยโพรเซสของ Aoi และโพรเซสของ Bitaro ไม่สามารถใช้ตัวแปรส่วนกลางร่วมกันได้
• โปรแกรมของคุณต้องไม่ใช้ข้อมูลนำเข้ามาตรฐานและข้อมูลส่งออกมาตรฐาน และต้องไม่สื่อสารกับไฟล์อื่นด้วยวิธีใด ๆ อย่างไรก็ตาม โปรแกรมของคุณสามารถส่งข้อมูลสำหรับแก้จุดบกพร่องไปยังช่องข้อผิดพลาดมาตรฐานได้

การคอมไพล์และทดลองรัน

คุณสามารถดาวน์โหลดไฟล์เก็บถาวรจากหน้าเว็บการแข่งขัน ซึ่งมีโปรแกรมตรวจตัวอย่างสำหรับทดสอบโปรแกรมของคุณ และมีไฟล์ซอร์สตัวอย่างของโปรแกรมคุณด้วย

โปรแกรมตรวจตัวอย่างคือไฟล์ grader.cpp ในการทดสอบโปรแกรม ให้วาง grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h ไว้ในไดเรกทอรีเดียวกัน และใช้คำสั่งต่อไปนี้เพื่อคอมไพล์โปรแกรม หรือจะรัน compile.sh ที่อยู่ในไฟล์เก็บถาวรแทนก็ได้

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

เมื่อคอมไพล์สำเร็จ จะได้ไฟล์ปฏิบัติการ grader

โปรดสังเกตว่าโปรแกรมตรวจจริงต่างจากโปรแกรมตรวจตัวอย่าง โปรแกรมตรวจตัวอย่างจะทำงานเป็นโพรเซสเดียว ซึ่งอ่านข้อมูลนำเข้าจากข้อมูลนำเข้ามาตรฐาน และเขียนผลลัพธ์ไปยังข้อมูลส่งออกมาตรฐานและช่องข้อผิดพลาดมาตรฐาน

ข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่าง

โปรแกรมตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

$$ \begin{gathered} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{gathered} $$

ข้อมูลส่งออกของโปรแกรมตรวจตัวอย่าง

โปรแกรมตรวจตัวอย่างส่งข้อมูลต่อไปนี้ไปยังข้อมูลส่งออกมาตรฐานและช่องข้อผิดพลาดมาตรฐาน (ใส่เครื่องหมายอัญประกาศเพื่อความชัดเจน)

• หากโปรแกรมของคุณถูกตัดสินว่า คำตอบผิด [1], [2], [3], [4] หรือ [6] โปรแกรมตรวจตัวอย่างจะเขียนชนิดของข้อผิดพลาด เช่น Wrong Answer [1] ไปยังช่องข้อผิดพลาดมาตรฐาน และจะไม่ส่งสิ่งใดไปยังข้อมูลส่งออกมาตรฐาน
• มิฉะนั้น ความยาวของสตริง $s$ ที่ฟังก์ชัน aoi คืนมาจะถูกส่งไปยังช่องข้อผิดพลาดมาตรฐานในรูปแบบ Accepted: 2024 นอกจากนี้ ความยาวของเส้นทางในการเรียกฟังก์ชัน answer ครั้งที่ $j+1$ ($0 \le j \le Q-1$) จะถูกส่งไปยังบรรทัดที่ $j+1$ ของข้อมูลส่งออกมาตรฐาน โปรแกรมตรวจตัวอย่าง ไม่ตรวจสอบ ว่าเส้นทางนั้นสั้นที่สุดหรือไม่

หากโปรแกรมของคุณเข้าเงื่อนไขคำตอบผิดหลายชนิด โปรแกรมตรวจตัวอย่างจะรายงานเพียงชนิดเดียว

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้:

• $2 \le N \le 10\,000$
• $1 \le M \le 20\,000$
• $1 \le Q \le 16$
• $1 \le K \le 300$
• $0 \le A_i<B_i \le N-1$ ($0 \le i \le M-1$)
• $(A_i,B_i) \ne (A_j,B_j)$ ($0 \le i<j \le M-1$)
• $1 \le C_i \le 10^{12}$ ($0 \le i \le M-1$)
• $1 \le T_j \le N-1$ ($0 \le j \le Q-1$)
• $T_j \ne T_k$ ($0 \le j<k \le Q-1$)
• $0 \le X_k \le M-1$ ($0 \le k \le K-1$)
• $X_k \ne X_l$ ($0 \le k<l \le K-1$)
• สามารถเดินทางจากเมืองใด ๆ ไปยังเมืองอื่นใดก็ได้โดยผ่านถนนบางสาย
• ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม

งานย่อย

หากโปรแกรมของคุณถูกตัดสินว่าเป็น คำตอบผิด [1]–[6] ชนิดใดก็ตาม (ดูรายละเอียดการเขียนโปรแกรม) หรือเกิดข้อผิดพลาดขณะทำงานชนิดใดก็ตาม เช่น TLE (เกินเวลาที่กำหนด), MLE (เกินหน่วยความจำที่กำหนด), การจบการทำงานผิดปกติ ฯลฯ ในกรณีทดสอบใดก็ตาม คะแนนของคุณจะเป็น 0 คะแนน

มิฉะนั้น การให้คะแนนจะขึ้นอยู่กับความยาวมากที่สุดของสตริง $s$ ที่ฟังก์ชัน aoi คืนมาในทุกกรณีทดสอบของโจทย์นี้ โดยแทนความยาวดังกล่าวด้วย $L$

• หาก $1561 \le L \le 12\,000$ จะได้ $\left\lfloor\frac{100\,000}{L-560}\right\rfloor$ คะแนน
• หาก $0 \le L \le 1560$ จะได้ 100 คะแนน

ในที่นี้ $\lfloor x\rfloor$ หมายถึงจำนวนเต็มที่มากที่สุดซึ่งไม่มากกว่า $x$

ตัวอย่างการสื่อสาร

ต่อไปนี้เป็นตัวอย่างข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่าง และการเรียกฟังก์ชันที่สอดคล้องกัน

ข้อมูลนำเข้า 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

ตัวอย่างการเรียกฟังก์ชัน

เส้นทางสั้นที่สุดจากเมือง $0$ ไปยังเมือง $1$ ทำได้โดยผ่านถนน $1$ แล้วถนน $0$ ตามลำดับ หรือผ่านเพียงถนน $2$ ดังนั้น ในการเรียกฟังก์ชัน answer ครั้งที่สองของตัวอย่างนี้ จะเรียก answer([2]) ก็ยอมรับได้เช่นกัน

ไฟล์ sample-01-in.txt ที่ดาวน์โหลดได้จากเว็บไซต์การแข่งขันตรงกับข้อมูลนำเข้าตัวอย่างที่ 1

ไฟล์ sample-01-in.txt และ sample-02-in.txt ที่อยู่ในชุดไฟล์ดาวน์โหลดจากเว็บไซต์การแข่งขัน สามารถใช้เป็นข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่างได้