루미 알고리즘

#1611다이아Chasing Rats

PO 2025 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

메모리 제한 2048 MB

Problem

Last year, no one managed to drive the giant rats out of Gothenburg (see the problem KATT:s and rats (https://open.kattis.com/problems/rats2)). Because of this, Olle has no choice but to take matters into his own hands and personally chase all of Gothenburg's rats into traps.

Gothenburg's sewers consist of N manholes, and there are M pipes connecting pairs of manholes. When Olle chases a rat, he places a trap in manhole T. He starts in manhole S, and the rat starts in manhole R. The goal is to get the rat to enter the trap in manhole T. Olle can move between manholes using the pipes. If he enters the same manhole as the rat, the rat will flee to an adjacent manhole. After chasing many rats, he has noticed that they are predictable: if he enters a manhole from a certain pipe, the rat will always flee to a specific manhole.

Unfortunately, Olle has noticed that some rats cannot be caught. He therefore needs your help Q times to determine whether it is possible to capture the rat given S, R, and T. All queries are independent of each other, and there is always exactly one rat in the sewers per query.

Input

The first line of input contains the integers N, M, and Q (3 ≤ N ≤ 10^5, 1 ≤ M,Q ≤ 10^5), the number of manholes, the number of pipes, and the number of queries.

The next M lines each describe a pipe. Each pipe is described by the integers u, v, a, b (1 ≤ u,v,a,b ≤ N, u ≠ v), where u, v indicate that there is a pipe between manholes u and v. a specifies that if Olle travels from u to v and a rat is in manhole v, it will flee to manhole a. b similarly specifies that if Olle is in manhole v and travels to u, the rat will flee to manhole b. It is also guaranteed that there is at most one pipe between each pair of manholes, the pipe (v,a) exists, the pipe (u,b) exists It is possible for Olle to travel between any two manholes.

Then follows Q lines, each containing the integers S, R, T (1 ≤ S,R,T ≤ N), describing that Olle wonders whether he can chase the rat in manhole R to manhole T if he starts in manhole S. It is guaranteed that T ≠ S, T ≠ R, and S ≠ R.

Note that this problem has a very large input size. Therefore, it is recommended to use fast input reading.

Output

Answer each query in the same order as the input. If Olle can chase the rat into the trap, print 1, otherwise print 0.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Let deg(u) be the number of pipes that connect to manhole u.

GroupPointsConstraints
15N, M ≤ 50, Q ≤ 100
211N, M ≤ 500, Q ≤ 10000
320Q=1, deg(u) ≤ 5 for all 1 ≤ u ≤ N.
423Q=1
512S and R are the same for all queries.
617T is the same for all queries.
710N, M ≤ 30000
82No additional constraints.

Explanation of Sample

The manholes are connected as follows. The escape routes for the rat are not drawn to reduce clutter.

(그림은 원문 저장소에서 볼 수 있습니다)

  • Question 1: There is no escape route for the rat that leads to manhole 4. Therefore, the answer is no.
  • Question 2: Olle can chase the rat into the trap directly.
  • Question 3: No matter how Olle chases the rat, he can never reach manhole 4 while the rat is in manhole 1. Therefore, the answer is no.

예제

예제 1

입력
5 5 3
1 2 1 2
2 3 1 1
3 1 3 1
4 1 5 1
5 1 3 1
2 1 4
4 1 5
2 1 5
출력
0
1
0

출처 표기

출처: Programmeringsolympiaden 2025년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.