นี่เป็นโจทย์แบบโต้ตอบ

ความเป็นมา

ครึ่งปีผ่านไป ในที่สุด I ก็ไม่สามารถดำเนินกิจการร้านต่อได้อีก เขาจึงตัดสินใจโอนร้านให้ผู้อื่น แล้วเป็นนักสำรวจเพื่อออกไปสำรวจโลกกว้างที่ยังไม่รู้จัก

ตามบันทึกในหนังสือโบราณ เขาพบพระราชวังใต้ดินที่สร้างโดยอารยธรรมที่ไม่รู้จัก อยู่ลึกเข้าไปในทะเลทรายอันกว้างใหญ่ พระราชวังประกอบด้วยถ้ำขนาดใหญ่ $N$ แห่ง และทางเดินสองทิศทาง $M$ สายที่เชื่อมถ้ำเหล่านี้ I สามารถใช้หนังสือโบราณระบุได้ว่าตนอยู่ในถ้ำใด แต่หนังสือไม่ได้บันทึกโครงสร้างการเชื่อมต่อของทางเดินทั้ง $M$ สาย จึงทำให้เขาค้นหาสมบัติมหาศาลที่ตามตำนานซ่อนอยู่ในพระราชวังได้ยาก

อย่างไรก็ตาม ตอนนี้ I ได้พบกลไกลึกลับที่ใช้รับข้อมูลเกี่ยวกับพระราชวังได้ เขาตัดสินใจใช้กลไกนี้เพื่อหาโครงสร้างการเชื่อมต่อของพระราชวัง โปรดช่วยเขาด้วย

รายละเอียดโจทย์

พระราชวังใต้ดินสามารถแทนด้วย กราฟไม่มีทิศทางอย่างง่าย ที่มีจุดยอด $N$ จุดและเส้นเชื่อม $M$ เส้น (กราฟอย่างง่ายมีเส้นเชื่อมโดยตรงระหว่างจุดยอดคู่ใด ๆ ได้ไม่เกินหนึ่งเส้น) ถ้ำมีหมายเลขตั้งแต่ $0$ ถึง $n-1$ ขณะนี้คุณไม่ทราบว่ามีเส้นเชื่อมใดบ้าง

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

1. เมื่อกำหนดหมายเลข $x$ ให้กลไก กลไกจะ สลับสถานะแหล่งกำเนิดแสงของถ้ำหมายเลข $x$ และถ้ำทุกแห่งที่มีทางเดินเชื่อมโดยตรงกับถ้ำหมายเลข $x$ กล่าวคือ แสงที่เปิดอยู่จะถูกปิด และแสงที่ปิดอยู่จะถูกเปิด
2. เมื่อกำหนดหมายเลข $x$ ให้กลไก กลไกจะแสดงสถานะแหล่งกำเนิดแสงของถ้ำหมายเลข $x$ ในขณะนั้น
3. เมื่อกำหนดหมายเลขสองตัว $x,y$ ให้กลไก หมายความว่าคุณยืนยันว่ามีทางเดินเชื่อมระหว่างถ้ำหมายเลข $x$ และ $y$ และให้กลไกบันทึกทางเดินนั้น
4. เมื่อกำหนดหมายเลข $x$ ให้กลไก กลไกจะตรวจว่าทางเดินทุกสายที่เชื่อมกับถ้ำหมายเลข $x$ ถูกบันทึกแล้วหรือไม่

จะเริ่มการทำงานครั้งถัดไปได้หลังจากการทำงานครั้งก่อนเสร็จสิ้นเท่านั้น กลไกไม่สามารถใช้งานได้อย่างไม่จำกัด จำนวนครั้งที่ใช้งานแต่ละแบบจึงมีขีดจำกัดตามลำดับคือ $L_m,L_q,M,L_c$ งานของคุณคือเขียนโปรแกรมช่วย I ตัดสินใจใช้กลไกอย่างเหมาะสม เพื่อค้นหาทางเดินทั้ง $M$ สายให้ถูกต้อง

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

คุณไม่จำเป็นและไม่ควรเขียนฟังก์ชันหลัก คุณต้องเขียนเฉพาะฟังก์ชัน explore(N, M) โดย N และ M คือจำนวนถ้ำและจำนวนทางเดินตามลำดับ คุณสามารถเรียกฟังก์ชันต่อไปนี้เพื่อโต้ตอบกับไลบรารีได้

1. modify(x)

   • ให้กลไกทำงานแบบที่ $1$ โดยใช้หมายเลข $x$
   • คุณต้องรับประกันว่า $0 \le x < N$ ฟังก์ชันนี้ไม่มีค่าคืนกลับ

2. query(x)

   • ให้กลไกทำงานแบบที่ $2$ โดยใช้หมายเลข $x$
   • คุณต้องรับประกันว่า $0 \le x < N$ ฟังก์ชันนี้คืนค่า $0$ หรือ $1$ เพื่อระบุว่าแหล่งกำเนิดแสงของถ้ำหมายเลข $x$ ในขณะนั้นปิดอยู่ ($0$) หรือเปิดอยู่ ($1$)

3. report(x, y)

   • ให้กลไกทำงานแบบที่ $3$ โดยใช้หมายเลข $x,y$
   • คุณต้องรับประกันว่า $0 \le x,y < N$ และ $x \ne y$ ฟังก์ชันนี้ไม่มีค่าคืนกลับ

4. check(x)

   • ให้กลไกทำงานแบบที่ $4$ โดยใช้หมายเลข $x$
   • คุณต้องรับประกันว่า $0 \le x < N$ ฟังก์ชันนี้คืนค่า $0$ หรือ $1$ โดยคืนค่า $1$ ก็ต่อเมื่อทางเดินทุกสายที่เชื่อมกับถ้ำหมายเลข $x$ ถูกบันทึกด้วยการทำงานแบบที่ $3$ แล้ว

ในการตรวจคำตอบ ไลบรารีจะเรียก explore เพียงหนึ่งครั้ง

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

รับประกันว่าภายใต้ขีดจำกัดจำนวนครั้งที่เรียก เวลาในการทำงานของไลบรารีไม่เกิน $1$ วินาที และไลบรารีใช้หน่วยความจำคงที่ไม่เกิน $128$ MB

วิธีเขียนโปรแกรม

ในไดเรกทอรีทำงานของผู้เข้าแข่งขันมีไฟล์ template_explore.cpp/c/pas ให้แล้ว ให้ทำสำเนาไฟล์นี้และเปลี่ยนชื่อเป็น explore.cpp/c/pas แล้วเขียนคำตอบต่อจากโค้ดในไฟล์นั้น

สำหรับภาษา C++ / C

• ตรวจให้แน่ใจว่าโปรแกรมขึ้นต้นด้วย #include "explore.h"
• ฟังก์ชัน explore ที่คุณต้องเขียนมีอินเทอร์เฟซดังนี้

void explore(int N, int M);

• ฟังก์ชันสำหรับโต้ตอบที่คุณสามารถเรียกได้มีอินเทอร์เฟซดังนี้

void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

สำหรับภาษา Pascal

• หมายเหตุ: ไวยากรณ์การเขียนอินเทอร์เฟซในโค้ด Pascal ค่อนข้างซับซ้อน ให้เขียนคำตอบต่อจากไฟล์ template_explore.pas ที่แจกให้โดยตรง แทนการเขียนโค้ดขึ้นมาใหม่ทั้งหมด
• ฟังก์ชัน explore ที่คุณต้องเขียนมีอินเทอร์เฟซดังนี้

procedure _explore(N, M : longint);

• หมายเหตุ: ชื่อฟังก์ชันคือ _explore ไม่ใช่ explore หากใช้ explore จะทำให้คอมไพล์ไม่ผ่าน
• ฟังก์ชันสำหรับโต้ตอบที่คุณสามารถเรียกได้มีอินเทอร์เฟซดังนี้

procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;

วิธีทดสอบโปรแกรม

ไฟล์ grader.cpp/c และ graderhelperlib.pas ในไดเรกทอรีของโจทย์เป็นตัวอย่างการเขียนไลบรารีที่เราให้ไว้ ไลบรารีที่ใช้ตรวจจริงมีการเขียนแตกต่างจากตัวอย่างนี้ ดังนั้นวิธีแก้ของผู้เข้าแข่งขันต้องไม่ขึ้นอยู่กับรายละเอียดการเขียนไลบรารี

1. สำหรับภาษา C/C++:

   • ให้ใช้คำสั่งต่อไปนี้ในไดเรกทอรีของโจทย์เพื่อคอมไพล์เป็นโปรแกรมที่เรียกใช้งานได้
   • สำหรับภาษา C:

gcc grader.c explore.c -o explore -O2 -lm

• สำหรับภาษา C++:

g++ grader.cpp explore.cpp -o explore -O2 -lm

1. สำหรับภาษา Pascal:

   • ให้ใช้คำสั่งต่อไปนี้ในไดเรกทอรีของโจทย์เพื่อคอมไพล์เป็นโปรแกรมที่เรียกใช้งานได้

fpc grader.pas -o"explore" -O2

1. สำหรับโปรแกรมที่คอมไพล์ได้:

   • โปรแกรมจะอ่านข้อมูลจากข้อมูลนำเข้ามาตรฐานในรูปแบบต่อไปนี้

บรรทัดแรกมีจำนวนเต็มสามตัว $L_m,L_q,L_c$ บรรทัดที่สองมีจำนวนเต็มสองตัว $N,M$ ซึ่งมีความหมายตามที่อธิบายไว้ในโจทย์

อีก $M$ บรรทัดถัดมา แต่ละบรรทัดมีจำนวนเต็มสองตัว $x,y$ อธิบายทางเดินที่เชื่อมระหว่างถ้ำหมายเลข $x$ และ $y$

• หลังอ่านข้อมูลแล้ว ไลบรารีจะเรียกฟังก์ชัน explore เพียงหนึ่งครั้งเพื่อทดสอบฟังก์ชันของคุณด้วยข้อมูลที่อ่านมา เมื่อฟังก์ชันของคุณคืนค่าตามปกติ ไลบรารีจะตรวจว่าการคำนวณของคุณถูกต้องหรือไม่ หากถูกต้องจะพิมพ์ Correct และข้อมูลเกี่ยวกับจำนวนครั้งที่เรียกฟังก์ชันโต้ตอบ มิฉะนั้นจะพิมพ์ข้อความผิดพลาดที่เกี่ยวข้อง

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

สมมติว่าโปรแกรมอ่านข้อมูลต่อไปนี้

100 200 300
3 2
0 1
1 2

จำนวนเต็มสามตัวในบรรทัดแรกระบุขีดจำกัดจำนวนครั้งที่เรียกการทำงานทั้งสามแบบ กล่าวคือ modify(x) เรียกได้ไม่เกิน $100$ ครั้ง query(x) เรียกได้ไม่เกิน $200$ ครั้ง และ check(x) เรียกได้ไม่เกิน $300$ ครั้ง

จำนวนเต็มสองตัวในบรรทัดที่สองระบุจำนวนถ้ำและจำนวนทางเดินตามลำดับ นั่นคือ $N=3,M=2$

จำนวนครั้งที่เรียก report(x, y) ต้องไม่เกิน $M$ ซึ่งในตัวอย่างนี้คือไม่เกิน $2$ ครั้ง

ต่อไปนี้เป็นกระบวนการโต้ตอบที่ถูกต้อง

คำอธิบายไฟล์ที่แจกให้

ในไดเรกทอรีของโจทย์มีไฟล์ดังต่อไปนี้

1. grader.cpp/c และ graderhelperlib.pas เป็นตัวอย่างการเขียนไลบรารีที่เราให้ไว้
2. explore.h และ grader.pas เป็นไฟล์ส่วนหัว ผู้เข้าแข่งขันไม่จำเป็นต้องสนใจรายละเอียดภายใน
3. template_explore.cpp/c/pas เป็นตัวอย่างซอร์สโค้ดคำตอบที่เราให้ไว้
4. explore1.in, explore2.in, explore3.in เป็นข้อมูลนำเข้าตัวอย่างสำหรับใช้ทดสอบ

โปรดสำรองไฟล์ทั้งหมดที่แจกให้ การตรวจคำตอบจะรับเฉพาะ explore.c/cpp/pas ในไดเรกทอรีของโจทย์นี้ และการแก้ไขไฟล์อื่นนอกเหนือจากโปรแกรมนี้จะไม่มีผล

การให้คะแนน

ในการตรวจคำตอบจริงจะรับเฉพาะ explore.cpp/c/pas การแก้ไขไฟล์อื่นในไดเรกทอรีของผู้เข้าแข่งขันไม่มีผลต่อการตรวจคำตอบ

โจทย์นี้ยังอยู่ภายใต้ข้อจำกัดเช่นเดียวกับโจทย์ทั่วไป ตัวอย่างเช่น การคอมไพล์ผิดพลาดจะทำให้ทั้งโจทย์ได้ $0$ คะแนน ส่วนข้อผิดพลาดขณะทำงาน การใช้เวลาเกินกำหนด หรือการใช้หน่วยความจำเกินกำหนด จะทำให้กรณีทดสอบนั้นได้ $0$ คะแนน คุณสามารถเข้าถึงได้เฉพาะตัวแปรที่ตนเองกำหนดและตัวแปรที่ไลบรารีให้มา รวมถึงพื้นที่หน่วยความจำที่สอดคล้องกับตัวแปรเหล่านั้นเท่านั้น การพยายามเข้าถึงพื้นที่อื่นอาจทำให้คอมไพล์ผิดพลาดหรือเกิดข้อผิดพลาดขณะทำงาน

นอกเหนือจากเงื่อนไขข้างต้น ในแต่ละกรณีทดสอบ คุณจะได้คะแนนเต็มก็ต่อเมื่อ

1. การเรียกฟังก์ชันทุกครั้งถูกต้องตามข้อกำหนด และจำนวนครั้งที่เรียก modify, query, check ไม่เกิน $L_m,L_q,L_c$ ตามลำดับ
2. เนื่องจาก report เรียกได้ไม่เกิน $M$ ครั้ง การเรียกแต่ละครั้งต้องบันทึกเส้นเชื่อมใหม่ที่มีอยู่จริง กล่าวคือ ทุกครั้งที่เรียก report(x, y) ต้องมีทางเดินเชื่อมระหว่างถ้ำหมายเลข $x$ และ $y$ และก่อนการเรียกครั้งนี้ต้องไม่เคยเรียก report(x, y) หรือ report(y, x) มาก่อน
3. ฟังก์ชัน explore ที่คุณเขียนคืนค่าตามปกติ
4. เมื่อฟังก์ชัน explore คืนค่า คุณได้บันทึกทางเดินทั้งหมด $M$ สายผ่านการเรียก report แล้ว

ข้อจำกัดและคำแนะนำ

โจทย์นี้มี $25$ กรณีทดสอบ แต่ละกรณีมีค่า $4$ คะแนน ขนาดข้อมูลและข้อจำกัดของแต่ละกรณีแสดงในตารางต่อไปนี้

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

ความหมายของตัวแปรในคอลัมน์คุณสมบัติพิเศษมีดังนี้

A: รับประกันว่าจุดยอดทุกจุดมีดีกรีเท่ากับ $1$ พอดี

B: รับประกันว่าสำหรับทุก $x>0$ มี $y<x$ เพียงหนึ่งตัวที่มีทางเดินเชื่อมโดยตรงระหว่างถ้ำหมายเลข $x$ และ $y$

C: มีการเรียงสับเปลี่ยน $p_0,p_1,\ldots,p_{N-1}$ ของ $0$ ถึง $N-1$ ซึ่งสำหรับทุก $1 \le i < N$ มีทางเดินเชื่อมระหว่างถ้ำหมายเลข $p_{i-1}$ และ $p_i$

D: รับประกันว่ากราฟเชื่อมต่อกัน

• คำแนะนำ: โปรแกรมของคุณสามารถแยกประเภทข้อมูลข้างต้นได้โดยดูหลักหน่วยของค่า $N$ ที่ได้รับ