Wesley's Anger Contest 4 Problem 7 - Squirrel Cities

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 3.0s
Java 5.0s
Python 5.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The squirrel nation is preparing to establish an advanced highway system to connect their cities. They are scattered among N different cities and would like to build a highway network such that there is a path between any two cities. There are M different potential highway plans that they are considering. The i^{th} highway plan connects cities a_i and b_i, with a bidirectional highway that has a durability of d_i, and takes t_i time to complete.

Each highway in the network must have a minimum durability, and a maximum amount of time to completion. Since the squirrels are indecisive, they will ask you Q questions. Each question is in the form of two integers, x_j, and y_j. They want you to determine whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least x_j, and each highway taking no longer that y_j time to complete.

For this problem, Python users are recommended to use PYPY over CPython.

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

2 \le N \le 100\,000
1 \le M \le 300\,000
1 \le Q \le 300\,000
1 \le d_i, t_i \le 10^9 for all 1 \le i \le M
1 \le x_j, y_j \le 10^9 for all 1 \le j \le Q

Subtask 1 [9%]

2 \le N \le 1\,000
1 \le M \le 3\,000
1 \le Q \le 3\,000

Subtask 2 [40%]

2 \le N \le 3\,000
1 \le M \le 9\,000

Subtask 3 [51%]

No additional constraints.

Input Specification

The first line of input contains 3 integers, N, M, and Q, representing the number of cities in the squirrel nation, the number of potential highway plans, and the number of questions they will ask you.

The next M lines describe the highway plans. The i^{th} line contains 4 integers, a_i, b_i, d_i, t_i, indicating that the i^{th} plan connects cities a_i and b_i with a bidirectional highway that has a durability of d_i, and takes t_i time to complete.

The next Q lines describe the questions the squirrels will ask. The j^{th} line contains 2 integers, x_j, y_j, indicating that the j^{th} question is asking whether it is possible to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least x_j, and each highway taking no longer that y_j time to complete.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output Q lines. The j^{th} line should contain the answer to the j^{th} query. If there is a way to build a highway network such that there is a path between any two cities, with each highway in the network having a durability of at least x_j, and each highway taking no longer that y_j time to complete, then output YES. Otherwise, output NO.

Sample Input 1

3 3 2
1 2 10 5
2 3 5 3
3 1 8 9
4 7
6 8

Sample Output 1

YES
NO

Sample Explanation 1

For the first question, the first and second highway plans can be built to satisfy the requirements.

For the second question, there is no possible way to build a highway network that satisfies all requirements.


Comments

There are no comments at the moment.