Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11BC2 - Robin

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/c11bc2


 

            Một ngày đẹp trời nọ, trên vương quốc của các Coders 2011, bỗng xuất hiện 1 lão phù thủy độc ác, lão phù thủy sirDat_LS đã có âm mưu thôn tính đất nước  của đức vua vodanh9x. Lão phù thủy này rất yêu con gái của đức vua là Rose và đã bắt Rose về nơi ở của lão ta.

            Đức vua vodanh9x liền tìm hiệp sĩ Robin và sẽ hứa gả con gái cho Robin nếu chàng cứu được công chúa Rose trở về. Lão phù thủy sirDat_LS độc ác với khuôn mặt rất ghê tởm khiến công chúa mỗi khi nhìn thấy hắn thì công chúa lại ngất đi.

            Và rồi, chàng Robin của chúng ta đã tìm được đến nơi ở của lão phù thủy. Nơi ở của lão là 1 mê cung có N phòng, và N phòng này liên thông với nhau và có đúng N-1 đường đi (coi mỗi đường đi là 1 cạnh).

            Nhưng khó khăn thay, lão phù thủy đã đánh số mỗi đường đi là 1 hoặc 2. Nếu chàng Robin muốn đến cứu công chúa, thì từ nơi xuất phát đến nơi có công chúa phải có ít nhất một đường đi được đánh số 2, nếu không chàng Robin sẽ chết.

            Yêu cầu: Cho m truy vấn (m <= 10^5) mỗi truy vấn có dạng (x,y), trong đó x là nơi xuất phát của Robin và y là nơi nhốt công chúa. Xác định đường đi ngắn nhất từ x đến y có cạnh co trọng số 2 hay không.

 

Input

 

Dòng đầu là số nguyên N (N <= 10^4) - số đỉnh của đồ thị và M  – số truy vấn.

            Từ dòng 2 đến dòng N: dòng thứ i chứa 2 số nguyên dương  x (x < i) và k (k <= 2) nghĩa là có cạnh nối giữa i và x và được đánh số là k.

            M dòng sau: mỗi dòng chứa 2 số x và y (Biểu thị cho truy vấn (x,y)).

 

Output

 

Với mỗi truy vấn, xuất ra “YES” nếu tồn tại đường đi có ít nhất 1 cạnh có trọng số 2, ngược lại xuất ra “NO”.

 

Example

Input:
6 7
1 1
1 2
3 1
1 2
5 2
1 3
5 1
2 1
2 1
1 2
2 4
1 2
Output:
YES
YES
NO
NO
NO
YES
NO
Độ phức tạp là O(M), ai accept với d0pt là O(MlogN) chỉ là may mắn accept.

            Đức vua vodanh9x liền tìm hiệp sĩ Robin và sẽ hứa gả con gái cho Robin nếu chàng cứu được công chúa Rose trở về. Lão phù thủy sirDat_LS độc ác với khuôn mặt rất ghê tởm khiến công chúa mỗi khi nhìn thấy hắn thì công chúa lại ngất đi.

            Và rồi, chàng Robin của chúng ta đã tìm được đến nơi ở của lão phù thủy. Nơi ở của lão là 1 mê cung có N phòng, và N phòng này liên thông với nhau và có đúng N-1 đường đi (coi mỗi đường đi là 1 cạnh).

            Nhưng khó khăn thay, lão phù thủy đã đánh số mỗi đường đi là 1 hoặc 2. Nếu chàng Robin muốn đến cứu công chúa, thì từ nới xuất phát đến nơi có công chúa phải có ít nhất một đường đi được đánh số 2, nếu không chàng Robin sẽ chết.

            Yêu cầu: Cho m truy vấn (m <= 10^7) mỗi truy vấn có dạng (x,y), trong đó x là nơi xuất phát của Robin và y là nơi nhốt công chúa. Xác định đường đi ngắn nhất từ x đến y có cạnh co trọng số 2 hay không.

Input:

            Dòng đầu là số nguyên N (N <= 10^6) - số đỉnh của đồ thị và M (M <= 10^7) – số truy vấn.

            Từ dòng 2 đến dòng N: dòng thứ i chứa 2 số nguyên dương  x (x < i) và k (k <= 2) nghĩa là có cạnh nối giữa i và x và được đánh số là k.

            M dòng sau: mỗi dòng chứa 2 số x và y (Biểu thị cho truy vấn (x,y))

Output

            Với mỗi truy vấn, xuất ra “YES” nếu tồn tại đường đi có ít nhất 1 cạnh có trọng số 2, ngược lại xuất ra “NO”.


Được gửi lên bởi:Duy Khanh Nguyen
Ngày:2011-11-27
Thời gian chạy:0.300s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Từ một bài tập codeforces

hide comments
2017-12-31 15:00:23
nhật hào sạch
2017-12-22 01:02:25
kham khảo thuật toán và code:
https://vietcodes.github.io/code/125/
2017-08-20 21:12:46 Ðặng Minh Tiến
https://kienthuc24h.com/c11bc2-spoj-robin/
2017-06-02 17:15:46
ac với độ phức tạp không may mắn :)
2017-03-28 18:50:59
cin + cout =100
scanf + printf = 100
:))))
2016-12-21 14:24:24 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/535/c11bc2-spoj/
2016-09-27 03:29:56
Code:
http://shink.in/FL3Gp
2016-07-13 19:04:34 THK6
1 đấm = DS :3
2016-05-24 10:50:42 Tiệp Anonymous
1 đấm =))
2016-04-26 16:28:40 even when you try to hurt me...
scanf + printf nhanh hơn nhé....
đọc hết dữ liệu vào rồi mới bắt đầu in kq , vừa đọc vừa in mãi k AC...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.