P8507 - Range Reachability Query

内存限制：128 MB 时间限制：10 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：0

You are given a directed acyclic graph with vertices and $m$ edges. The vertices are labeled by $1, 2, \dots, n$ , and the edges are labeled by $1, 2, \dots, m$ .

You will be given queries. In the th query, you will be given four integers $u_{i}$ , $v_{i}$ , $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq m$ ). You need to answer whether vertex $u_{i}$ can reach vertex $v_{i}$ when only edges labeled by ( $l_{i} \leq k \leq r_{i}$ ) are available.

The first line contains a single integer ( $1 \leq T \leq 10$ ), the number of test cases. For each test case:

The first line contains three integers and ( $2 \leq n \leq 50, 000$ , $1 \leq m \leq 100, 000$ , $1 \leq q \leq 50, 000$ ), denoting the number of vertices, the number of edges, and the number of queries.

Each of the following lines contains two integers $u_{i}$ and $v_{i}$ ( $1 \leq u_{i} < v_{i} \leq n$ ), denoting a directed edge from vertex $u_{i}$ to vertex $v_{i}$ .

In the next lines, the th line contains four integers $u_{i}$ , $v_{i}$ , $l_{i}$ and $r_{i}$ ( $1 \leq u_{i} < v_{i} \leq n$ , $1 \leq l_{i} \leq r_{i} \leq m$ ), describing the -th query.

For each query, print a single line. If vertex

u_{i}

can reach vertex

v_{i}

when only edges labeled by

k

(

l_{i} \leq k \leq r_{i}

) are available, print ''

YES

''. Otherwise, print ''

NO

''.

NO
YES
YES
YES
NO

2022 杭电多校第三场

8507: Range Reachability Query

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签