ต้นงิ้วไม่กี่ต้นในบ้านเกิดยังคงเติบโตอยู่ในความทรงจำของ N ที่ค่อย ๆ เลือนราง ความทรงจำของ N เกี่ยวกับบ้านเกิดแทนได้ด้วยลำดับ $[a_0,a_1,\ldots,a_{n-1}]$ ที่มีความยาว $n$

ต้นงิ้วแต่ละต้นในบ้านเกิดมีรูปร่างเป็นต้นไม้ไม่มีรากที่จุดยอดมีหมายเลข ภาพจำของ N เกี่ยวกับต้นงิ้วหนึ่งต้นอธิบายได้ด้วยช่วง $[l,r)$ ของความทรงจำเกี่ยวกับบ้านเกิดของเธอ:

• ต้นไม้นี้มีจุดยอด $k=r-l+2$ จุด หมายเลขตั้งแต่ $0$ ถึง $k-1$
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ คือลำดับ Prüfer ของต้นไม้นี้ ดูนิยามของลำดับ Prüfer ในหัวข้อ “คำใบ้”

ขณะรำลึกถึงอดีต N ถามคุณ $m$ คำถาม โดยคำถามที่ $i$ ($0\le i<m$) คือ:

• ในต้นงิ้วที่ตรงกับช่วง $[l_i,r_i)$ ของความทรงจำเกี่ยวกับบ้านเกิด จุดยอด $x_i,y_i$ อยู่ติดกันหรือไม่?

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

ผู้เข้าแข่งขันไม่จำเป็นและไม่ควรเขียนฟังก์ชัน main

ผู้เข้าแข่งขันต้องแน่ใจว่าไฟล์ซอร์สที่ส่งมีการรวมเฮดเดอร์ kapok.h โดยเพิ่มโค้ดต่อไปนี้ไว้ตอนต้นโปรแกรม:

#include "kapok.h"

ผู้เข้าแข่งขันต้องเขียนฟังก์ชันต่อไปนี้ในไฟล์ซอร์ส kapok.cpp ที่ส่ง:

std::vector<bool> kapok(int c, int n, int m,
    std::vector<int> a, std::vector<int> l, std::vector<int>
    r, std::vector<int> x, std::vector<int> y);

• $c,n,m$ แทนหมายเลขชุดทดสอบ ความยาวลำดับความทรงจำเกี่ยวกับบ้านเกิด และจำนวนคำถามตามลำดับ $c=0$ หมายความว่าชุดทดสอบนี้เป็นตัวอย่าง
• $a$ แทนลำดับความทรงจำเกี่ยวกับบ้านเกิด
• $l,r$ แทนปลายทั้งสองของช่วงที่กำหนดในแต่ละคำถามตามลำดับ
• $x,y$ แทนหมายเลขจุดยอดทั้งสองที่กำหนดในแต่ละคำถามตามลำดับ
• ฟังก์ชันนี้ต้องคืนลำดับ $f_0,f_1,\ldots,f_{m-1}$ ที่มีความยาวเท่ากับ $m$ พอดี โดย $f_i$ ($0\le i<m$) แทนผลลัพธ์ของคำถามที่ $i$
• สำหรับแต่ละชุดทดสอบ โปรแกรมตรวจจะเรียกฟังก์ชันนี้หนึ่งครั้งพอดี

ไฟล์ template_kapok.cpp ในไดเรกทอรีของโจทย์นี้เป็นโค้ดตัวอย่างที่จัดเตรียมไว้ ผู้เข้าแข่งขันสามารถใช้เป็นข้อมูลอ้างอิงในการเขียนโค้ดของตนเอง

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

ผู้เข้าแข่งขันสามารถใช้คำสั่งต่อไปนี้ในไดเรกทอรีของโจทย์เพื่อคอมไพล์เป็นไฟล์ปฏิบัติการ:

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

สำหรับไฟล์ปฏิบัติการ kapok ที่คอมไพล์ได้:

• ไฟล์ปฏิบัติการจะอ่านข้อมูลจากอินพุตมาตรฐานในรูปแบบต่อไปนี้:

  • บรรทัดแรกมีจำนวนเต็มไม่เป็นลบสามจำนวน $c,n,m$
  • บรรทัดที่สองมีจำนวนเต็มไม่เป็นลบ $n$ จำนวน $a_0,a_1,\ldots,a_{n-1}$
  • บรรทัดที่ $i+3$ ($0\le i<m$) มีจำนวนเต็มไม่เป็นลบสี่จำนวน $l_i,r_i,x_i,y_i$

• ไฟล์ปฏิบัติการจะเขียนข้อมูลไปยังเอาต์พุตมาตรฐานในรูปแบบต่อไปนี้:

  • บรรทัดที่ $i+1$ ($0\le i<m$) มีจำนวนเต็มไม่เป็นลบหนึ่งจำนวน โดย $0$ หมายความว่า $f_i$ เป็น false และ $1$ หมายความว่า $f_i$ เป็น true

ตัวอย่าง

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

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

ข้อมูลส่งออก 1

1
0
1

หมายเหตุ

• ต้นไม้ที่ตรงกับช่วง $[0,3)$ มีจุดยอด $5$ จุด ลำดับ Prüfer คือ $[2,0,2]$ และเซตเส้นเชื่อมคือ $\{(1,2),(0,3),(0,2),(2,4)\}$ ดังนั้นจุดยอด $0,2$ อยู่ติดกัน
• ต้นไม้ที่ตรงกับช่วง $[3,5)$ มีจุดยอด $4$ จุด ลำดับ Prüfer คือ $[3,0]$ และเซตเส้นเชื่อมคือ $\{(1,3),(0,2),(0,3)\}$ ดังนั้นจุดยอด $1,2$ ไม่อยู่ติดกัน
• ต้นไม้ที่ตรงกับช่วง $[0,0)$ มีจุดยอด $2$ จุด ลำดับ Prüfer ว่าง และเส้นเชื่อมเพียงเส้นเดียวคือ $(0,1)$ ดังนั้นจุดยอด $0,1$ อยู่ติดกัน

ตัวอย่าง 2

ดู kapok/kapok2.in และ kapok/kapok2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้เป็นไปตามข้อจำกัดของชุดทดสอบ $3\sim5$

ตัวอย่าง 3

ดู kapok/kapok3.in และ kapok/kapok3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้เป็นไปตามข้อจำกัดของชุดทดสอบ $3\sim5$

ข้อจำกัด

สำหรับข้อมูลทดสอบทั้งหมด:

• $1\le n,m\le2\times10^5$
• สำหรับทุก $0\le i<n$ มี $0\le a_i<n+2$
• สำหรับทุก $0\le i<m$ มี $0\le l_i\le r_i\le n$ และ $0\le x_i,y_i<r_i-l_i+2$

• สมบัติพิเศษ A: สำหรับทุก $0\le i<m$ หลังจากกำหนด $l_i,r_i$ แล้ว $x_i,y_i$ ถูกสุ่มอย่างอิสระและสม่ำเสมอจากคู่จุดยอดแบบมีลำดับทั้งหมดที่เป็นไปตามข้อจำกัด

คำใบ้

สำหรับต้นไม้ไม่มีราก $T$ ที่จุดยอดมีหมายเลขตั้งแต่ $0$ ถึง $c-1$ ($c\ge2$):

• ดำเนินการ $c-2$ ครั้งตามลำดับ โดยการดำเนินการที่ $i$ ($0\le i<c-2$) เป็นดังนี้:

  • หาจุดยอดใบ $v_i$ ที่มีหมายเลขน้อยที่สุดในขณะนั้น
  • บันทึกหมายเลข $p_i$ ของจุดยอดเพียงจุดเดียวที่อยู่ติดกับมัน
  • จากนั้นลบ $v_i$ และเส้นเชื่อมเพียงเส้นเดียวที่ติดกับมันออกจาก $T$

• ลำดับ $[p_0,p_1,\ldots,p_{c-3}]$ ที่มีความยาว $c-2$ ซึ่งได้จากกระบวนการนี้คือลำดับ Prüfer ของ $T$