oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

nemo Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

nemo.html

Problem Description

Due to an accident, Martin the clownfish has lost his only son, Nemo. Now, Martin wants to know if it is possible for him to even find Nemo.

In the oceans, there are a total of N different places connected by E different convection currents which brings you from one place to another almost instantly. For the sake of simplicity, we assume that the convection currents are bi-directional.

However, convection currents do not function all the time. Some ocean currents might only be available in the night while others during the day only. For this problem, we shall assume that each convection current has a specified 'opening time' and a 'closing time'. The convection current will be functional between the 'opening time' and 'closing time' inclusive.

For convenience, places are labelled from 0 to N-1 and Martin is currently at location X while Nemo is currently at location Y. Martin wants to know whether it is possible to get to Nemo assuming the current time is T.

To do so, Rar the Cat was enlisted to help Martin out. Rar the Cat has noticed that all the convection currents will open before any of the convection currents close. In other words, no 'opening time' will be later than any of the 'closing times' of other currents.

Input

The first line of input will contain 2 integers, N and E.

Subsequent E lines will contain 4 integer on each line: A, B, O, C. This means that there exist a convection current from place A to place B with 'opening time' O and 'closing time' C.

This problem has multiple testcases, the next line will contain an integer TC, denoting the number of testcases that will follow.

There will be a single testcase per subsequent TC lines. Each testcase contains 3 integers, X, Y and T. You are to answer if Martin can travel from X to Y instantly at time T.

Output

For each testcase, output 'Y' on a single line if Martin can travel from X to Y instantly at time T. If not, output 'N' on a single line instead.

Limits

0 ≤ A, B, X, Y < N

0 ≤ T, O, C ≤ 2000000000

It is guaranteed that A ≠ B and X ≠ Y

Unless otherwise stated, there will not be more than 100000 testcases. (TC ≤ 100000)

Subtasks

Subtask 1 (7 marks): N = 2, E = 1, TC = 10

Subtask 2 (25 marks): 0 < N ≤ 50000, 0 < E ≤ 100000, all O = 0, all C = 2000000000

Subtask 3 (29 marks): 0 < N ≤ 50000, 0 < E ≤ 100000, TC= 10

Subtask 4 (39 marks): 0 < N ≤ 50000, 0 < E ≤ 100000

Subtask 5 (0 marks): Sample Testcases

Sample Input 1

2 1
0 1 13 17
10
0 1 10
1 0 11
0 1 12
0 1 13
0 1 14
1 0 15
0 1 16
0 1 17
1 0 18
0 1 19

Sample Output 1

N
N
N
Y
Y
Y
Y
Y
N
N

Sample Input 2

6 8
0 1 5 11
0 2 0 15
1 3 9 20
1 4 7 15
2 3 2 12
2 4 9 15
3 5 7 20
4 5 10 10
10
0 5 10
0 5 13
4 5 10
2 5 13
4 5 20
1 5 20
0 5 21
0 2 3
0 3 3
0 4 3

Sample Output 2

Y
Y
Y
Y
N
Y
N
Y
Y
N

Tags

RI NOI Selection Test 2014, Graph Theory, Union Find Disjoint Set

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1721s32MBMinimum
225251s32MBMinimum
329631s32MBMinimum
4391231s32MBMinimum
5021s32MBMinimum

Attachments

Attachment Filesize Last Updated
3.1.in.txt91B4 May 2020, 15:33:25
3.1.out.txt20B4 May 2020, 15:33:25

Judge Compile Command

g++-8 ans.cpp -o nemo -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.