分数: 366 分
问题陈述
Takahashi 设计了一个图表,包括 N 节点和 M 有向边。节点编号从 1 to N.
每个节点 i 被分配了一个区间 数轴上的 [L_i, R_i] 。另外,每个节点 i 已记录到达位置 P_i 和出发位置 Q_i.
每个有向边都有一个起始节点 U_j,结束节点 V_j和分支标签 B_j (0 or 1)。即使同一个元组 (U_j, V_j, B_j) 出现多次,每次出现都被视为单独的边缘。
该图称为 有效的二叉决策树 如果满足以下所有条件:
有根树结构: 该图形成一个有节点的有根树 1 作为根。也就是说,以下所有条件均成立:
出度约束:对于每个节点,最多有一个带标签的出边(从该节点开始的边) 0,且最多有一个带标签的出边 1.
间隔遏制:对于每条边 u \to v, L_u < L_v 和 R_v < R_u 按住。也就是说,子进程的间隔严格包含在父进程的间隔内。
位置一致性:对于每条边 u \to v, P_v = Q_u 成立。也就是说,边的起始节点的出发位置与边的结束节点的到达位置相匹配。
左右排序:当两个标签 0 边缘和标签 1 边存在于节点 u,让它们各自的端点为 x 和 y,条件 R_x < L_y 成立。
确定给定图是否是有效的二叉决策树。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- N + M \leq 2 \times 10^5
- -10^9 \leq L_i < R_i \leq 10^9
- -10^9 \leq P_i \leq 10^9
- -10^9 \leq Q_i \leq 10^9
- 1 \leq U_j, V_j \leq N
- U_j \neq V_j
- B_j \in \{0, 1\}
- 相同的元组 (U_j, V_j, B_j) 可以多次给出。
- 所有输入均为整数。
输入
N M L_1 R_1 P_1 Q_1 L_2 R_2 P_2 Q_2 \vdots L_N R_N P_N Q_N U_1 V_1 B_1 U_2 V_2 B_2 \vdots U_M V_M B_M
- 第一行包含节点数 N 和边数 M,用空格分隔。
- 以下 N 行给出每个节点的信息。
- 的 (1 + i)第行包含左端点 L_i,右端点 R_i,到达位置 P_i,以及出发位置 节点的 Q_i 节点的 i,用空格分隔。
- 以下 M 行给出了每条边的信息。
- 的 (1 + N + j)-第行包含起始节点 U_j,结束节点 V_j和分支标签 B_j 的 j第一条边,以空格分隔。
输出
如果给定图是有效的二叉决策树,则输出 YES;否则,输出 NO.
样本输入 1
3 2 0 10 0 100 1 3 100 200 5 8 100 300 1 2 0 1 3 1
示例输出 1
YES
示例输入 2
2 2 0 10 0 5 2 8 5 7 1 2 0 1 2 0
示例输出 2
NO
示例输入 3
10 9 -100 100 0 10 -90 -10 10 20 10 90 10 30 -80 -50 20 40 -40 -20 20 50 20 80 30 60 -75 -60 40 70 -38 -35 50 80 -30 -25 50 90 30 70 60 100 1 2 0 1 3 1 2 4 0 2 5 1 3 6 1 4 7 1 5 8 0 5 9 1 6 10 0
示例输出 3
YES
示例输入 4
20 19 -1000 1000 0 1 -900 -100 1 2 0 900 1 3 -850 -500 2 4 -400 -150 2 5 20 600 3 6 550 850 3 7 -840 -700 4 8 -650 -550 4 9 -350 -200 5 10 30 200 6 11 250 500 6 12 600 800 7 13 -830 -800 8 14 -640 -600 9 15 -340 -300 10 16 -280 -220 10 17 300 450 12 18 620 680 13 19 700 780 13 20 1 2 0 1 3 1 2 4 0 2 5 1 3 6 0 3 7 1 4 8 0 4 9 1 5 10 0 6 11 0 6 12 1 7 13 1 8 14 0 9 15 1 10 16 0 10 17 1 12 18 0 13 19 0 13 20 1
示例输出 4
NO
示例输入 5
1 0 -1000000000 1000000000 -1000000000 1000000000
示例输出 5
YES