ผลต่างระหว่างรุ่นของ "Baltic2013"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
== Ball Machine ==
 
== Ball Machine ==
  
เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้  โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N  แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก  เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง  ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานตามการดำเนินการได้สองแบบ:
+
เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้  โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N  แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก  เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง  ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานตามการดำเนินการได้สองแบบ คือ:
  
1. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root  ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น  ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root   
+
'''แบบที่ 1'''. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root  ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น  ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root   
  
 
ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ
 
ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ
แถว 9: แถว 9:
 
ตัวอย่างเช่น ถ้าเราใส่ลูกบอลสองลูกลงในเครื่องจักรในรูปด้านล่าง  ลูกบอลทั้งสองจะไหลไปที่โหนด 1 และ 3  ลูกบอลลูกแรกจะไหลจากโหนด 4 ไปยังโหนด 3 เนื่องจากโหนด 3 นั้นว่างอยู่และมีโหนด 1 อยู่ในต้นไม้ย่อยของมัน (ที่ประกอบด้วยโหนด 3 และ 1)  จากนั้นลูกบอลจะไหลจากโหนด 3 ไปยังโหนด 1  ลูกบอลลูกที่สองจะไหลจากโหนด 4 ไปยังโหนด 3 และหยุดที่ตำแหน่งนั้น
 
ตัวอย่างเช่น ถ้าเราใส่ลูกบอลสองลูกลงในเครื่องจักรในรูปด้านล่าง  ลูกบอลทั้งสองจะไหลไปที่โหนด 1 และ 3  ลูกบอลลูกแรกจะไหลจากโหนด 4 ไปยังโหนด 3 เนื่องจากโหนด 3 นั้นว่างอยู่และมีโหนด 1 อยู่ในต้นไม้ย่อยของมัน (ที่ประกอบด้วยโหนด 3 และ 1)  จากนั้นลูกบอลจะไหลจากโหนด 3 ไปยังโหนด 1  ลูกบอลลูกที่สองจะไหลจากโหนด 4 ไปยังโหนด 3 และหยุดที่ตำแหน่งนั้น
  
 
+
'''แบบที่ 2'''. นำลูกบอลออกจากบางโหนด: โหนดนั้นจะเปลี่ยนสถานะเป็นว่าง  จากนั้นลูกบอลที่อยู่ด้านบน (ถ้ามี) ก็จะไหลลงมา  เมื่อใดที่โหนดพ่อแม่ของโหนดที่ว่างมีลูกบอล ลูกบอลจะไหลลงไปยังโหนดนั้น  
2. นำลูกบอลออกจากบางโหนด: โหนดนั้นจะเปลี่ยนสถานะเป็นว่าง  จากนั้นลูกบอลที่อยู่ด้านบน (ถ้ามี) ก็จะไหลลงมา  เมื่อใดที่โหนดพ่อแม่ของโหนดที่ว่างมีลูกบอล ลูกบอลจะไหลลงไปยังโหนดนั้น  
 
  
 
ถ้าเรานำลูกบอลออกจากโหนด 5, 7, และ 8 (ตามลำดับดังกล่าว) จากเครื่องจักรในรูปด้านล่าง โหนด 1, 2, และ 3 จะเปลี่ยนสถานะเป็นโหนดว่าง
 
ถ้าเรานำลูกบอลออกจากโหนด 5, 7, และ 8 (ตามลำดับดังกล่าว) จากเครื่องจักรในรูปด้านล่าง โหนด 1, 2, และ 3 จะเปลี่ยนสถานะเป็นโหนดว่าง
แถว 37: แถว 36:
  
 
== Pipes ==
 
== Pipes ==
 +
 +
เมือง Hotham ตกเป็นเป้าหมายของการทำลายของ Jester อีกครั้งหนึ่ง  คราวนี้ เป้าหมายของ Jester คือระบบจ่ายน้ำ  น้ำจืดของเมือง Hotham เก็บอยู่ที่อ่างเก็บน้ำ N แห่ง เชื่อมต่อกันด้วยท่อน้ำ M ท่อ  ระบบท่อนี้รับประกันว่ามีเส้นทางอย่างน้อยหนึ่งเส้น (อาจจะประกอบด้วยท่อหลายท่อ) จากอ่างเก็บน้ำหนึ่งไปยังอ่างเก็บน้ำอื่น ๆ  นอกจากนี้ทุก ๆ ท่อเชื่อมต่อกับอ่างเก็บน้ำสองแห่งที่แตกต่างกัน และจะมีท่อไม่เกินหนึ่งท่อสำหรับคู่ของอ่างเก็บน้ำใด ๆ
 +
 +
Jester ได้บุกรุกไปยังบางท่อและได้เริ่มนำน้ำออกจากท่อ  ด้วยอารมณ์ศิลปินของ Jester เขารับประกันว่าน้ำที่ไหลออกจากท่อใด ๆ จะมีค่าเป็นเลขคู่ (หน่วยเป็นลูกบาศก์เมตรต่อวินาที)  ถ้าน้ำไหลออกจากท่อที่เชื่อมระหว่างอ่างเก็บน้ำ u และ v ด้วยอัตรา 2d  ลบม/ว แล้ว อ่างเก็บน้ำ u และ v จะเสียน้ำเท่ากันในอัตรา d ลบม/ว
 +
 +
เพื่อเพิ่มความสับสนอลเวง(และครื้นเครง) Jester ยังได้ปั้มน้ำเข้าไปในบางท่อ  เช่นเดียวกัน เขารับประกันว่าน้ำที่ปั้มเข้าไปที่ท่อจะเป็นเลขคู่  ถ้าท่อที่เชื่อมระหว่างอ่างเก็บน้ำ u และ v ได้รับการปั้มน้ำเข้าไป 2p ลบม/ว แล้ว อ่างเก็บน้ำ u และ v จะมีน้ำเพิ่มขึ้นในอัตราอ่างละ p ลบม/ว
 +
 +
อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำของอ่างเก็บน้ำใด ๆ คือผลรวมของน้ำที่เข้าและน้ำที่เสียไปจากท่อที่ติดกับอ่างเก็บน้ำนั้น  กล่าวคือ ถ้าอ่างเก็บน้ำติดกับท่อที่น้ำถูกนำออกในอัตรา 2d1, 2d2, ..., 2da ลบม/ว และติดกับท่อที่มีน้ำถูกปั้มเข้ามาในอัตรา 2p1, 2p2, ..., 2pb ลบม/ว แล้ว  อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำในอ่างเก็บน้ำนั้นคือ p1+p2+...+pb-d1-d2-...-da
 +
 +
ผู้ว่าเมือง Hotham ได้ติดตั้งเซ็นเซอร์ไว้ที่อ่างเก็บน้ำ แต่ไม่ได้ติดที่ท่อน้ำ  ดังนั้น เขาจึงสามารถตรวจสอบได้เฉพาะอัตราการเปลี่ยนแปลงสุทธิของน้ำในแต่ละอ่างเก็บน้ำ แต่ไม่ใช่ที่ท่อน้ำ
 +
 +
หน้าที่ของคุณคือเขียนโปรแกรมเพื่อช่วยผู้ว่า  โปรแกรมของคุณจะรับข้อมูลเกี่ยวกับเครือข่ายระบบน้ำ และอัตราการเปลี่ยนแปลงสุทธิของแต่ละอ่างเก็บน้ำ  จากนั้นโปรแกรมจะต้องคำนวณว่าข้อมูลดังกล่าวพอเพียงที่จะระบุแผนการของ Jester ได้รูปแบบเดียวหรือไม่  จะกล่าวว่า แผนการถูกระบุได้แบบเดียว ถ้ามีความเป็นไปได้ในการกำหนดการไหลออกของน้ำและปั้มน้ำเข้าที่ท่อต่าง ๆ ได้รูปแบบเดียวเท่านั้น  นอกจากนี้สังเกตว่า ไม่จำเป็นที่อัตราการไหลของน้ำที่ท่อต่าง ๆ ไม่จำเป็นต้องเท่ากันทั้งหมด    ถ้ามีคำตอบรูปแบบเดียว ให้โปรแกรมของคุณพิมพ์รูปแบบนั้นออกมา

รุ่นแก้ไขปัจจุบันเมื่อ 03:30, 22 เมษายน 2556

Ball Machine

เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้ โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานตามการดำเนินการได้สองแบบ คือ:

แบบที่ 1. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root

ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ

ตัวอย่างเช่น ถ้าเราใส่ลูกบอลสองลูกลงในเครื่องจักรในรูปด้านล่าง ลูกบอลทั้งสองจะไหลไปที่โหนด 1 และ 3 ลูกบอลลูกแรกจะไหลจากโหนด 4 ไปยังโหนด 3 เนื่องจากโหนด 3 นั้นว่างอยู่และมีโหนด 1 อยู่ในต้นไม้ย่อยของมัน (ที่ประกอบด้วยโหนด 3 และ 1) จากนั้นลูกบอลจะไหลจากโหนด 3 ไปยังโหนด 1 ลูกบอลลูกที่สองจะไหลจากโหนด 4 ไปยังโหนด 3 และหยุดที่ตำแหน่งนั้น

แบบที่ 2. นำลูกบอลออกจากบางโหนด: โหนดนั้นจะเปลี่ยนสถานะเป็นว่าง จากนั้นลูกบอลที่อยู่ด้านบน (ถ้ามี) ก็จะไหลลงมา เมื่อใดที่โหนดพ่อแม่ของโหนดที่ว่างมีลูกบอล ลูกบอลจะไหลลงไปยังโหนดนั้น

ถ้าเรานำลูกบอลออกจากโหนด 5, 7, และ 8 (ตามลำดับดังกล่าว) จากเครื่องจักรในรูปด้านล่าง โหนด 1, 2, และ 3 จะเปลี่ยนสถานะเป็นโหนดว่าง

Input

  • บรรทัดแรกระบุจำนวนเต็ม N และ Q แทนจำนวนโหนดและจำนวนการดำเนินการ
  • อีก N บรรทัดหลังจากนั้นเป็นข้อมูลอธิบายเครื่องจักร แต่ละบรรทัดจะระบุจำนวนเต็มหนึ่งจำนวน เป็นหมายเลขของโหนด กล่าวคือ ในบรรทัดที่ i ของกลุ่มบรรทัดเหล่านี้จะระบุหมายเลขของโหนดพ่อแม่ของโหนดที่ i, หรือค่า 0 ถ้าโหนด i เห็นโหนด root ของต้นไม้ดังกล่าว
  • อีกแต่ละ Q บรรทัดถัดจากนั้นจะมีจำนวนเต็มสองจำนวนที่ระบุการดำเนินการ การดำเนินการแบบที่ 1 จะระบุด้วยบรรทัดในรูปแบบ 1 k โดยที่ k แทนจำนวนของลูกบอลที่จะใส่เข้าไปในเครื่องจักร สำหรับการดำเนินการแบบที่ 2 จะระบุด้วยบรรทัดในรูปแบบ 2 x โดยที่ x แทนหมายเลขของโหนดที่จะนำลูกบอลออก รับประกันว่าการดำเนินการต่าง ๆ นั้นถูกต้อง กล่าวคือ จะไม่มีการเพิ่มลูกบอลมากกว่าจำนวนโหนดว่างในเครื่องและจะไม่มีการนำลูกบอลออกจากโหนดที่ว่าง

Output

สำหรับการดำเนินการประเภทที่ 1 ให้พิมพ์หมายเลขของโหนดสุดท้ายที่ลูกบอลลูกสุดท้ายที่ใส่ไปไปตกอยู่ สำหรับการดำเนินการประเภทที่ 2 ให้พิมพ์จำนวนลูกบอลที่ไหลลงมาหลังจากการนำลูกบอลออกจากโหนดที่ระบุ

ข้อจำกัด

  • N,Q <= 100 000
  • ในข้อมูลทดสอบที่มีคะแนน 25 คะแนน แต่ละโหนดจะมี 0 หรือ 2 โหนด นอกจากนี้ ทุก ๆ โหนดที่ไม่มีลูกจะมีระยะทางจากโหนด root เท่ากันทั้งหมด
  • ในข้อมูลทดสอบที่มีคะแนน 30 คะแนน แต่ละการดำเนินการจะถูกเรียกโดยรับประกันว่าจะไม่มีลูกบอลไหลลงมาหลังจากการดำเนินการที่ 2
  • ในข้อมูลทดสอบที่มีคะแนน 40 คะแนน จะมีการทำงานตามดำเนินการประเภทที่ 1 แค่ครั้งเดียว และจะเป็นกิจกรรมแรกเท่านั้น
  • เซตของข้อมูลทดสอบทั้ง 3 เซตที่กล่าวมานั้น pairwise disjoint กัน

Numbers

Pipes

เมือง Hotham ตกเป็นเป้าหมายของการทำลายของ Jester อีกครั้งหนึ่ง คราวนี้ เป้าหมายของ Jester คือระบบจ่ายน้ำ น้ำจืดของเมือง Hotham เก็บอยู่ที่อ่างเก็บน้ำ N แห่ง เชื่อมต่อกันด้วยท่อน้ำ M ท่อ ระบบท่อนี้รับประกันว่ามีเส้นทางอย่างน้อยหนึ่งเส้น (อาจจะประกอบด้วยท่อหลายท่อ) จากอ่างเก็บน้ำหนึ่งไปยังอ่างเก็บน้ำอื่น ๆ นอกจากนี้ทุก ๆ ท่อเชื่อมต่อกับอ่างเก็บน้ำสองแห่งที่แตกต่างกัน และจะมีท่อไม่เกินหนึ่งท่อสำหรับคู่ของอ่างเก็บน้ำใด ๆ

Jester ได้บุกรุกไปยังบางท่อและได้เริ่มนำน้ำออกจากท่อ ด้วยอารมณ์ศิลปินของ Jester เขารับประกันว่าน้ำที่ไหลออกจากท่อใด ๆ จะมีค่าเป็นเลขคู่ (หน่วยเป็นลูกบาศก์เมตรต่อวินาที) ถ้าน้ำไหลออกจากท่อที่เชื่อมระหว่างอ่างเก็บน้ำ u และ v ด้วยอัตรา 2d ลบม/ว แล้ว อ่างเก็บน้ำ u และ v จะเสียน้ำเท่ากันในอัตรา d ลบม/ว

เพื่อเพิ่มความสับสนอลเวง(และครื้นเครง) Jester ยังได้ปั้มน้ำเข้าไปในบางท่อ เช่นเดียวกัน เขารับประกันว่าน้ำที่ปั้มเข้าไปที่ท่อจะเป็นเลขคู่ ถ้าท่อที่เชื่อมระหว่างอ่างเก็บน้ำ u และ v ได้รับการปั้มน้ำเข้าไป 2p ลบม/ว แล้ว อ่างเก็บน้ำ u และ v จะมีน้ำเพิ่มขึ้นในอัตราอ่างละ p ลบม/ว

อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำของอ่างเก็บน้ำใด ๆ คือผลรวมของน้ำที่เข้าและน้ำที่เสียไปจากท่อที่ติดกับอ่างเก็บน้ำนั้น กล่าวคือ ถ้าอ่างเก็บน้ำติดกับท่อที่น้ำถูกนำออกในอัตรา 2d1, 2d2, ..., 2da ลบม/ว และติดกับท่อที่มีน้ำถูกปั้มเข้ามาในอัตรา 2p1, 2p2, ..., 2pb ลบม/ว แล้ว อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำในอ่างเก็บน้ำนั้นคือ p1+p2+...+pb-d1-d2-...-da

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

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