C - 二分決定木の検証 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 個のノードと M 本の有向辺からなるグラフを設計しました。ノードには 1 から N までの番号が付いています。

各ノード i には、数直線上の区間 [L_i, R_i] が割り当てられています。また、各ノード i には到着位置 P_i と出発位置 Q_i が記録されています。

各有向辺には始点 U_j、終点 V_j、および分岐ラベル B_j（0 または 1）が付いています。同じ (U_j, V_j, B_j) の組が複数回現れる場合も、それぞれ別の辺として扱います。

このグラフが、次の条件をすべて満たすとき、正しい二分決定木であるとします。

  1. 根付き木の構造：ノード 1 を根とする根付き木になっている。すなわち、以下をすべて満たす。

    • ノード 1 に入る辺（ノード 1 を終点とする辺）がない。

    • ノード 2, 3, \dots, N にはそれぞれちょうど 1 本の入る辺がある。

    • ノード 1 から有向辺を繰り返したどることで、すべてのノードに到達できる。

  2. 出次数の制約：各ノードについて、ラベル 0 の出る辺（そのノードを始点とする辺）は高々 1 本、ラベル 1 の出る辺も高々 1 本である。

  3. 区間の包含：各辺 u \to v について、L_u < L_v かつ R_v < R_u が成り立つ。すなわち、子の区間が親の区間に厳密に含まれる。

  4. 位置の整合性：各辺 u \to v について、P_v = Q_u が成り立つ。すなわち、辺の始点の出発位置と終点の到着位置が一致する。

  5. 左右の順序：あるノード u からラベル 0 の辺とラベル 1 の辺がともに存在するとき、それぞれの終点を 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
  • 1 行目には、ノード数 N と辺数 M がスペース区切りで与えられる。
  • 続く N 行では、各ノードの情報が与えられる。
  • 1 + i 行目には、ノード i の区間の左端 L_i、右端 R_i、到着位置 P_i、出発位置 Q_i がスペース区切りで与えられる。
  • 続く M 行では、辺の情報が与えられる。
  • 1 + N + j 行目には、j 番目の辺の始点 U_j、終点 V_j、分岐ラベル B_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

Score : 366 pts

Problem Statement

Takahashi has designed a graph consisting of N nodes and M directed edges. The nodes are numbered from 1 to N.

Each node i is assigned an interval [L_i, R_i] on the number line. Additionally, each node i has a recorded arrival position P_i and departure position Q_i.

Each directed edge has a starting node U_j, an ending node V_j, and a branch label B_j (0 or 1). Even if the same tuple (U_j, V_j, B_j) appears multiple times, each occurrence is treated as a separate edge.

This graph is called a valid binary decision tree if it satisfies all of the following conditions:

  1. Rooted tree structure: The graph forms a rooted tree with node 1 as the root. That is, all of the following hold:

    • There are no edges entering node 1 (no edges with node 1 as their endpoint).

    • Each of nodes 2, 3, \dots, N has exactly one entering edge.

    • All nodes are reachable from node 1 by repeatedly following directed edges.

  2. Out-degree constraint: For each node, there is at most one outgoing edge (an edge starting from that node) with label 0, and at most one outgoing edge with label 1.

  3. Interval containment: For each edge u \to v, L_u < L_v and R_v < R_u hold. That is, the child's interval is strictly contained within the parent's interval.

  4. Position consistency: For each edge u \to v, P_v = Q_u holds. That is, the departure position of the edge's starting node matches the arrival position of the edge's ending node.

  5. Left-right ordering: When both a label 0 edge and a label 1 edge exist from a node u, letting their respective endpoints be x and y, the condition R_x < L_y holds.

Determine whether the given graph is a valid binary decision tree.

Constraints

  • 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\}
  • The same tuple (U_j, V_j, B_j) may be given multiple times.
  • All inputs are integers.

Input

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
  • The first line contains the number of nodes N and the number of edges M, separated by a space.
  • The following N lines give the information for each node.
  • The (1 + i)-th line contains the left endpoint L_i, right endpoint R_i, arrival position P_i, and departure position Q_i of node i, separated by spaces.
  • The following M lines give the information for each edge.
  • The (1 + N + j)-th line contains the starting node U_j, ending node V_j, and branch label B_j of the j-th edge, separated by spaces.

Output

If the given graph is a valid binary decision tree, output YES; otherwise, output NO.

Sample Input 1

3 2
0 10 0 100
1 3 100 200
5 8 100 300
1 2 0
1 3 1

Sample Output 1

YES

Sample Input 2

2 2
0 10 0 5
2 8 5 7
1 2 0
1 2 0

Sample Output 2

NO

Sample Input 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

Sample Output 3

YES

Sample Input 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

Sample Output 4

NO

Sample Input 5

1 0
-1000000000 1000000000 -1000000000 1000000000

Sample Output 5

YES