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

สถานะหิมะตกของถนนแต่ละสายเปลี่ยนไปในแต่ละวัน ในแต่ละวัน ถนนแต่ละสายจะอยู่ในสถานะมีหิมะตกหรือไม่มีหิมะตกอย่างใดอย่างหนึ่ง สถานะจะไม่เปลี่ยนระหว่างวัน

Anya และ Boris ทำงานที่กรมการขนส่งของรัสเซีย Anya อยู่ฝ่ายจัดการข้อมูลถนน ส่วน Boris อยู่ฝ่ายตอบคำถามของประชาชน คำถามของประชาชนคือ ในการเดินทางจากเมือง $0$ ซึ่งเป็นเมืองหลวงของรัสเซียไปยังอีกเมืองหนึ่ง ต้องผ่านถนนที่มีหิมะตกอย่างน้อยกี่สาย โดยปกติ เมื่อได้รับคำถาม Boris จะติดต่อกับ Anya แล้วตอบประชาชน

ครั้งนี้ รัสเซียจะจัดการแข่งขันเขียนโปรแกรมชิงแชมป์โลกเป็นเวลา $Q$ วัน คาดว่าในช่วงการแข่งขันเครือข่ายสื่อสารจะหนาแน่น ทำให้ Anya และ Boris ติดต่อกันโดยตรงได้ยาก จึงตกลงสื่อสารกันดังนี้:

• Anya ได้รับข้อมูลหิมะตกของวันนั้นในตอนต้นวัน แล้วส่งข้อมูลไปยังเซิร์ฟเวอร์ตัวกลาง
• เมื่อ Boris ได้รับคำถามจากประชาชน เขาจะตอบโดยติดต่อกับเซิร์ฟเวอร์ตัวกลาง

อย่างไรก็ตาม การสื่อสารของ Anya และ Boris มีข้อจำกัดดังต่อไปนี้:

• เซิร์ฟเวอร์ตัวกลางมีความจุ $L=1\,000$ บิต Anya เก็บข้อมูลไว้ได้ไม่เกิน $L$ บิต
• ข้อมูลทั้งหมดในเซิร์ฟเวอร์ตัวกลางถูกกำหนดเป็น 0 เมื่อต้นวัน
• ในการติดต่อกับเซิร์ฟเวอร์หนึ่งครั้ง Boris อ่านข้อมูลได้หนึ่งบิต ณ ตำแหน่งที่ระบุ
• เพื่อตอบคำถามแต่ละข้อ Boris ติดต่อกับเซิร์ฟเวอร์ได้ไม่เกิน 20 ครั้ง

คุณรู้จักกับผู้อำนวยการกรมการขนส่ง จึงได้รับหน้าที่คิดกลยุทธ์ให้ Anya และ Boris

降雪情報: ข้อมูลหิมะตก; 中継サーバ: เซิร์ฟเวอร์ตัวกลาง; 容量 L ビット: ความจุ $L$ บิต; 質問ごとに20ビットまで: ไม่เกิน 20 บิตต่อคำถาม; 市民: ประชาชน

งานที่ต้องทำ

จงเขียนโปรแกรมที่ใช้กลยุทธ์ของ Anya และ Boris ซึ่งสามารถตอบคำถามของประชาชนได้ถูกต้อง

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

คุณต้องส่งไฟล์สองไฟล์ที่เขียนด้วยภาษาโปรแกรมเดียวกัน

ไฟล์แรกชื่อ Anya.c หรือ Anya.cpp ไฟล์นี้ใช้กลยุทธ์ของ Anya และต้องเขียนรูทีนสองรูทีนต่อไปนี้ โปรแกรมต้อง include Anyalib.h

• void InitAnya(int N, int A[], int B[])

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

  • อาร์กิวเมนต์ N แทนจำนวนเมือง
  • อาร์กิวเมนต์ A[] และ B[] เป็นลำดับที่มีความยาว $N-1$ ทั้งคู่ และแทนข้อมูลการเชื่อมต่อของถนน สมาชิก A[i] และ B[i] ($0 \le i \le N-2$) เป็นจำนวนเต็มที่ระบุว่าถนน $i$ เชื่อมเมือง A[i] กับ B[i] แบบสองทิศทาง และเป็นไปตาม $0 \le \texttt{A[i]} < \texttt{B[i]} \le N-1$

• void Anya(int C[])

  ฟังก์ชันนี้ถูกเรียก $Q$ ครั้งหลังจากเรียก InitAnya การเรียกนี้สอดคล้องกับการที่ Anya เลือกลำดับบิตที่จะเก็บในเซิร์ฟเวอร์ตัวกลาง หลังจากข้อมูลหิมะตกบนถนนได้รับการปรับปรุงในตอนต้นวัน

  • อาร์กิวเมนต์ C[] เป็นลำดับความยาว $N-1$ แทนข้อมูลหิมะตกบนถนน สมาชิก C[i] ($0 \le i \le N-2$) เป็นจำนวนเต็ม 0 หรือ 1 ที่แทนข้อมูลของถนน $i$ โดย C[i] = 1 หมายถึงถนน $i$ มีหิมะตก และ C[i] = 0 หมายถึงไม่มีหิมะตก

  ภายในฟังก์ชัน Anya สามารถเรียกฟังก์ชันต่อไปนี้ได้:

  • void Save(int place, int bit)

    ฟังก์ชันนี้แทนการที่ Anya บันทึกบิตลงในเซิร์ฟเวอร์ตัวกลาง

    • อาร์กิวเมนต์ place ระบุตำแหน่งที่จะเขียนบิต ต้องเป็นจำนวนเต็มตั้งแต่ $0$ ถึง $L-1$ หากเรียกด้วยค่านอกช่วงนี้ จะตัดสินว่าคำตอบผิด [1] นอกจากนี้ ในการเรียก Anya แต่ละครั้ง ห้ามเรียกฟังก์ชันนี้ด้วยค่า place เดียวกันตั้งแต่สองครั้งขึ้นไป หากเรียกด้วยค่าเดียวกันสองครั้ง จะตัดสินว่าคำตอบผิด [2]
    • อาร์กิวเมนต์ bit เป็นจำนวนเต็มแทนบิตที่จะเขียน ต้องเป็น 0 หรือ 1 หากเรียกด้วยค่าอื่น จะตัดสินว่าคำตอบผิด [3]

    หลังเรียก Save บิตที่ตำแหน่ง place ของเซิร์ฟเวอร์ตัวกลางจะมีค่าเป็น bit

    หากการเรียก Save ถูกตัดสินว่าคำตอบผิด โปรแกรมจะสิ้นสุดทันที

  ก่อนเรียก Anya ทุกครั้ง บิตทั้งหมดในเซิร์ฟเวอร์ตัวกลางจะถูกกำหนดเป็น 0 เสมอ กล่าวคือ ตำแหน่งที่ไม่ได้บันทึกด้วย Save จะมีค่า 0 เมื่อ Anya สิ้นสุดการทำงาน

ไฟล์ที่สองชื่อ Boris.c หรือ Boris.cpp ไฟล์นี้ใช้กลยุทธ์ของ Boris และต้องเขียนรูทีนสองรูทีนต่อไปนี้ โปรแกรมต้อง include Borislib.h

• void InitBoris(int N, int A[], int B[])

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

  • อาร์กิวเมนต์ N แทนจำนวนเมือง
  • อาร์กิวเมนต์ A[] และ B[] เป็นลำดับที่มีความยาว $N-1$ ทั้งคู่ และแทนข้อมูลการเชื่อมต่อของถนน สมาชิก A[i] และ B[i] ($0 \le i \le N-2$) เป็นจำนวนเต็มที่ระบุว่าถนน $i$ เชื่อมเมือง A[i] กับ B[i] แบบสองทิศทาง และเป็นไปตาม $0 \le \texttt{A[i]} < \texttt{B[i]} \le N-1$

• int Boris(int city)

  ฟังก์ชันนี้ถูกเรียกหลายครั้งหลังเรียก InitBoris โดยสอดคล้องกับการกระทำของ Boris เพื่อตอบคำถามประชาชน

  • อาร์กิวเมนต์ city แทนคำถามของประชาชน เป็นจำนวนเต็มตั้งแต่ $1$ ถึง $N-1$ ซึ่งหมายถึงคำถามว่า การเดินทางจากเมือง $0$ ไปยังเมือง city ต้องผ่านถนนที่มีหิมะตกอย่างน้อยกี่สาย
  • ฟังก์ชัน Boris ต้องคืนจำนวนเต็มตั้งแต่ $0$ ถึง $N-1$ ซึ่งเป็นคำตอบของคำถาม หากคืนจำนวนเต็มนอกช่วงนี้ จะตัดสินว่าคำตอบผิด [4] หากคำตอบไม่ถูกต้อง จะตัดสินว่าคำตอบผิด [7]

  ภายในฟังก์ชัน Boris สามารถเรียกฟังก์ชันต่อไปนี้ได้:

  • int Ask(int place)

    ฟังก์ชันนี้แทนการที่ Boris อ่านบิตจากเซิร์ฟเวอร์ตัวกลาง

    • อาร์กิวเมนต์ place ระบุตำแหน่งที่จะอ่านบิต ต้องเป็นจำนวนเต็มตั้งแต่ $0$ ถึง $L-1$ หากเรียกด้วยค่านอกช่วงนี้ จะตัดสินว่าคำตอบผิด [5]

    ค่าที่ Ask คืนเป็นจำนวนเต็ม 0 หรือ 1 แทนค่าของบิตที่ตำแหน่ง place ในเซิร์ฟเวอร์ตัวกลาง นอกจากนี้ ในการเรียก Boris แต่ละครั้ง เรียก Ask ได้ไม่เกิน 20 ครั้ง หากเรียกเกิน 20 ครั้ง จะตัดสินว่าคำตอบผิด [6]

  หากการเรียก Ask ถูกตัดสินว่าคำตอบผิด โปรแกรมจะสิ้นสุดทันที

ขั้นตอนการตรวจให้คะแนน

การตรวจให้คะแนนดำเนินตามขั้นตอนต่อไปนี้ หากตัดสินว่าคำตอบผิด โปรแกรมจะสิ้นสุดทันที

1. เรียก InitAnya และ InitBoris อย่างละหนึ่งครั้งตามลำดับนี้ เพื่อให้ข้อมูลถนน

2. สำหรับ $i=1,\ldots,Q$ ดำเนินการต่อไปนี้ตามลำดับ:

   1. เรียก Anya เพียงหนึ่งครั้ง ซึ่งสอดคล้องกับการที่ Anya เลือกลำดับบิตที่จะเก็บในเซิร์ฟเวอร์ตัวกลาง หลังข้อมูลหิมะตกได้รับการปรับปรุงเมื่อต้นวัน
   2. เรียก Boris จำนวน $D_i$ ครั้ง โดย $D_i$ คือจำนวนคำถามจากประชาชนในวันที่ $i$ อาร์กิวเมนต์ในการเรียกครั้งที่ $j$ ($1 \le j \le D_i$) คือ $R_{ij}$ ($1 \le R_{ij} \le N-1$) ในการเรียกครั้งที่ $j$ หากค่าที่ Boris คืนไม่เท่ากับจำนวนถนนที่มีหิมะตกน้อยที่สุดที่ต้องผ่านเพื่อเดินทางจากเมือง $0$ ไปยังเมือง $R_{ij}$ จะตัดสินว่าคำตอบผิด

3. หากไม่เคยถูกตัดสินว่าคำตอบผิด จะตัดสินว่าคำตอบถูกต้อง

หมายเหตุสำคัญ

• เวลาและหน่วยความจำที่วัดคือส่วนของขั้นตอน (1) และ (2) ในหัวข้อ “ขั้นตอนการตรวจให้คะแนน” หากคำตอบถูกต้อง ในขั้นตอน (2) จะเรียก Anya รวม $Q$ ครั้ง และเรียก Boris รวม $D_1+\cdots+D_Q$ ครั้ง
• Anya และ Boris ไม่สามารถทราบค่าของ $D_1,\ldots,D_Q$ ได้
• ฟังก์ชัน Boris จะไม่ได้รับข้อมูลที่บอกว่า Anya ปรับปรุงข้อมูลในเซิร์ฟเวอร์ตัวกลางเมื่อใด
• คุณสามารถเขียนรูทีนอื่นสำหรับใช้ภายในหรือประกาศตัวแปรโกลบอลได้อย่างอิสระ อย่างไรก็ตาม โปรแกรมสองไฟล์ที่ส่งจะถูกลิงก์รวมกับโปรแกรมตรวจให้คะแนนเป็นไฟล์ปฏิบัติการเดียว ดังนั้นตัวแปรโกลบอลและรูทีนภายในทั้งหมดของแต่ละไฟล์ (ยกเว้น InitAnya, Anya, InitBoris, Boris) ต้องประกาศเป็น static เพื่อหลีกเลี่ยงการรบกวนกับไฟล์อื่น ในการตรวจจริง โปรแกรมจะทำงานเป็นสองโพรเซส คือฝั่ง Anya และฝั่ง Boris ดังนั้นทั้งสองฝั่งจึงไม่สามารถใช้ตัวแปรโกลบอลร่วมกันได้
• โปรแกรมที่ส่งห้ามติดต่อกับข้อมูลนำเข้ามาตรฐาน ข้อมูลส่งออกมาตรฐาน หรือไฟล์อื่นด้วยวิธีใดก็ตาม

วิธีคอมไพล์และเรียกใช้

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

โปรแกรมตรวจให้คะแนนตัวอย่างประกอบด้วยไฟล์เดียว คือ grader.c หรือ grader.cpp หากโปรแกรมของคุณคือ Anya.c และ Boris.c หรือ Anya.cpp และ Boris.cpp ให้ทดสอบโดยเรียกคำสั่งดังนี้:

• สำหรับ C

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• สำหรับ C++

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

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

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

ภาพรวมของโปรแกรมตรวจให้คะแนนตัวอย่าง

โปรแกรมตรวจให้คะแนนตัวอย่างเรียกฟังก์ชันตามหัวข้อ “ขั้นตอนการตรวจให้คะแนน”

โปรดระวังว่าพฤติกรรมต่อไปนี้แตกต่างจากโปรแกรมตรวจให้คะแนนจริง:

• โปรแกรมตัวอย่างไม่ตรวจคำตอบผิด [7] แต่จะส่งออกค่าที่ฟังก์ชัน Boris คืนสำหรับแต่ละคำถามแทน

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

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

• บรรทัดแรกมีจำนวนเต็ม $N$ แทนจำนวนเมือง
• บรรทัดที่ $i+1$ ($0 \le i \le N-2$) ของ $N-1$ บรรทัดถัดไปมีจำนวนเต็ม $A_i,B_i$ คั่นด้วยช่องว่าง ซึ่งหมายถึงถนน $i$ เชื่อมเมือง $A_i$ กับ $B_i$ แบบสองทิศทาง
• บรรทัดถัดไปมีจำนวนเต็ม $Q$ หมายถึงการแข่งขันจัดเป็นเวลา $Q$ วัน
• บรรทัดที่ $i$ ($1 \le i \le Q$) ของ $Q$ บรรทัดถัดไปมีสตริง $S_i$ ความยาว $N-1$ และจำนวนเต็ม $D_i+1$ จำนวน คั่นด้วยช่องว่าง $S_i$ แทนข้อมูลหิมะตกวันที่ $i$ อักขระตัวที่ $j+1$ จากซ้าย ($0 \le j \le N-2$) เป็น 1 ถ้าถนน $j$ มีหิมะตก และเป็น 0 ถ้าไม่มีหิมะตก จำนวนเต็มตัวแรกใน $D_i+1$ จำนวนคือ $D_i$ และ $D_i$ จำนวนถัดไปคือ $R_{i1},\ldots,R_{iD_i}$ ซึ่งหมายความว่าในวันที่ $i$ คำถามที่ $j$ ($1 \le j \le D_i$) ถามจำนวนถนนที่มีหิมะตกน้อยที่สุดที่ต้องผ่านเพื่อเดินทางจากเมือง $0$ ไปยังเมือง $R_{ij}$

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

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

• หากระหว่างทำงานถูกตัดสินว่าคำตอบผิด จะส่งออกชนิดของคำตอบผิด เช่น Wrong Answer [1] แล้วสิ้นสุดการทำงาน
• หากการเรียก Boris ทั้ง $D_i$ ครั้งหลังการเรียก Anya ครั้งที่ $i$ ($1 \le i \le Q$) ไม่ถูกตัดสินว่าคำตอบผิด จะส่งออกจำนวนเต็ม $D_i$ จำนวนในหนึ่งบรรทัด คั่นด้วยช่องว่าง จำนวนเต็มตัวที่ $j$ ($1 \le j \le D_i$) คือค่าที่ $\operatorname{Boris}(R_{ij})$ คืน

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

ข้อจำกัด

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

• $2 \le N \le 500$
• $1 \le Q \le 500$
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$)
• $1 \le D_j$ ($1 \le j \le Q$)
• $D_1+\cdots+D_Q \le 500$
• สามารถเดินทางระหว่างเมืองที่แตกต่างกันสองเมืองใด ๆ ได้โดยผ่านถนนบางสาย

งานย่อย

งานย่อย 1 [15 คะแนน]

• $N \le 20$

งานย่อย 2 [5 คะแนน]

• $N \le 100$

งานย่อย 3 [35 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $A_i=i$ ($0 \le i \le N-2$)
• $B_i=i+1$ ($0 \le i \le N-2$)

งานย่อย 4 [45 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่างการโต้ตอบ

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

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

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

ตัวอย่างการเรียกรูทีน

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

อาร์กิวเมนต์ที่ส่งให้ InitAnya(...), InitBoris(...) และการเรียก Anya(...) ครั้งแรกและครั้งที่สองในตัวอย่างนี้เป็นดังต่อไปนี้: