a676. 青蛙跳跳跳 - Zero1 Online Judge System

Content

池塘內有一隻青蛙名叫比比，池塘內亦有 N 片荷葉，這些荷葉分別編號為 1, 2, 3, ..., N。每片荷葉有其 ( x, y ) 坐標，為簡單起見，我們假設荷葉的面積很少，但剛好可以讓比比在上面停留。比比的彈跳非常之強，但平衡力則有很嚴重的問題，因此他只能垂直 (y) 方向或水平 (x) 方向跳 ( 即不能斜向跳 )，但只要是這兩個方向，則無論多遠比比都能跳到。現在我們想知道若比比身在某一片荷葉時，他是否有辦法可以跳到另一片指定的荷葉上去。

Input

輸入的第一行上有兩個整數 N, Q，它們分別代表荷葉的數目及要查詣的數目。( 2 <= N <= 20000, 1 <= Q <= 5000 )

隨後的 N 行中，每行有一對正整數，順序代表著荷葉 i 所在的坐標位置 ( xi , yi )。( 1 <= xi , yi <= 10000 )

再隨後有 Q 行中，每行也有一對正整數 Sj, Dj，它代表我們想知若比比身在荷葉 Sj 上，他是否可以直接或間接 ( 經過一至多片中間荷葉 ) 跳到荷葉 Dj 上去？( 1 <= Sj , Dj <= N )

Output

輸出資料應含有 Q 行，每行應有一個整數，這個整數應是 0 或 1。簡單來說，若比比可以由荷葉 Sj 直接或間接跳到荷葉 Dj 時，則第 j 行上應輸出一個 1，否則應輸出一個 0。

Sample Input #1

Sample Output #1

1
1
0

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1M
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1M
不公開測資點#9 (10%): 1.0s , <1M

Hint ：

#非官方測試數據

Tags:

出處:

MOI 2018 [管理者：

lamkinun@gma... (Kinda Lam)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」