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

trucks Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

trucks.html

Problem Description

Peanut has recently taken up a truck driving job! (what?) He now needs to deliver some stuff to some people in his city. His city can be represented in a graph of N nodes and N-1 edges, with each road i connecting nodes Ai and Bi. Every two nodes are connected by exactly one path. Peanut's factory is located at node 0. Each road will also have a certain length Wi, which is defined by the amount of time it takes to traverse that edge.

Today, Peanut has Q deliveries to make, each delivery i being at time Ti and toward node Mi. Peanut can send his minions to deliver these goods, and they must leave exactly at time Ti and are not allowed to "wait" at nodes, travel back and forth edges, or anything to stall time. They must go straight to the destination node using the shortest path. (they do not need to return.)

Now, here is the problem. To save electricity, his city has decided to close roads at certain times, so each road i will only be open from time Si to Ei inclusive. To clarify, Peanut's minions can enter the road within the time period. His exit time is not limited. Therefore, help Peanut determine if he is able to execute each delivery.

Input

The first line of input will contain two integers, N and Q.
The next N-1 lines of input will contain five integers for each edge, representing Ai, Bi, Wi, Si and Ei.
The next Q lines of input will contain two integers each, Mi and Ti for each delivery.

Output

Your program should output either a "YES" or a "NO" on a single line for each delivery, representing whether the delivery can be done.

Limits

1 ≤ N ≤ 100 000. 1 ≤ Q ≤ 300 000. 0 ≤ Wi, Si, Ei, ≤ 1 000 000.
Subtask 1 (12%): All road lengths are 0, Q ≤ 20.
Subtask 2 (14%): Q ≤ 20.
Subtask 3 (23%): Si = 0.
Subtask 4 (24%): 1 ≤ N ≤ 1 000. 1 ≤ Q ≤ 3 000.
Subtask 5 (27%): No other constaints apply.
Subtask 6 (0%): Sample testcases.

Sample Input 1

3 5
0 1 0 3 5
1 2 0 1 3
2 3
2 5
2 1
1 4
1 2

Sample Output 1

YES
NO
NO
YES
NO

Sample Input 2

6 3
0 5 2 2 6
4 5 2 2 6
2 5 1 4 5
0 3 3 1 5
1 3 2 2 4
4 1
4 2
3 5

Sample Output 2

NO
YES
YES

Tags

Graph Theory, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
112201s256MBMinimum
214201s256MBMinimum
323201s256MBMinimum
424201s256MBMinimum
527201s256MBMinimum
6021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o trucks -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.