← 返回题目列表

AtCoder · awc0090_c

C. 二元决策树的验证

中文机器翻译题面 查看原题

分数: 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. 有根树结构: 该图形成一个有节点的有根树 1 作为根。也就是说,以下所有条件均成立:

    • 没有边进入节点 1 (没有带有节点的边 1 作为终点)。
    • 每个节点 2, 3, \dots, N 仅有一个进入边缘。
    • 所有节点均可从节点访问 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