F - Connecting Points Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

2 次元平面上に N 頂点 0 辺のグラフ G があります。頂点には 1 から N までの番号が付いており、頂点 i は座標 (x_i,y_i) にあります。

G の頂点 u,v に対して、u,v の距離 d(u,v) をマンハッタン距離 d(u,v)=|x_u-x_v|+|y_u-y_v| で定義します。

また、G の 2 つの連結成分 A,B に対して、A,B の頂点集合をそれぞれ V(A),V(B) としたとき、A,B の距離 d(A,B) を d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace で定義します。

以下で説明されるクエリを Q 個処理してください。クエリは次の 3 種類のいずれかです。

  • 1 a b : G の頂点数を n としたとき、頂点 n+1 の座標を (x_{n+1},y_{n+1})=(a,b) として、G に頂点 n+1 を追加する。
  • 2 : G の頂点数を n、連結成分数を m とする。
    • m=1 のとき、-1 を出力する。
    • m\geq 2 のとき、距離が最小である連結成分をすべてマージし、その最小の距離の値を出力する。厳密には、G の連結成分を A_1,A_2,\ldots,A_m として、\displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j) とする。同じ連結成分にない頂点の組 (u,v)\ (1\leq u\lt v\leq n) であって d(u,v)=k を満たすようなものすべてについて、頂点 u と v の間に辺を張る。その後、k を出力する。
  • 3 u v : 頂点 u,v が同じ連結成分にあるならば Yes を、そうでないならば No を出力する。

制約

  • 2\leq N\leq 1500
  • 1\leq Q\leq 1500
  • 0\leq x_i,y_i\leq 10^9
  • 1 種類目のクエリについて、0\leq a,b\leq 10^9
  • 3 種類目のクエリについて、そのクエリを処理する直前の G の頂点数を n としたとき、1\leq u\lt v\leq n
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。\mathrm{query}_i は i 番目に処理するクエリである。

N Q
x_1 y_1
x_2 y_2
\vdots
x_N y_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の 3 種類のいずれかの形式で与えられる。

1 a b

2

3 u v

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

出力例 1

No
1
Yes
2
No
3
Yes
-1
0

はじめ、頂点 1,2,3,4 はそれぞれ座標 (3,4),(3,3),(7,3),(2,2) にあります。

  • 1 番目のクエリについて、頂点 1 と 2 は連結でないため、No を出力します。
  • 2 番目のクエリについて、連結成分は 4 つあり、各連結成分に含まれる頂点集合は \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace です。異なる連結成分間の距離の最小値は 1 であり、頂点 1 と 2 の間に辺が張られます。1 を出力します。
  • 3 番目のクエリについて、頂点 1 と 2 は連結であるため、Yes を出力します。
  • 4 番目のクエリについて、座標 (6,4) に頂点 5 を追加します。
  • 5 番目のクエリについて、連結成分は 4 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace です。異なる連結成分間の距離の最小値は 2 であり、頂点 2 と 4 の間および頂点 3 と 5 の間に辺が張られます。2 を出力します。
  • 6 番目のクエリについて、頂点 2 と 5 は連結でないため、No を出力します。
  • 7 番目のクエリについて、連結成分は 2 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace です。異なる連結成分間の距離の最小値は 3 であり、頂点 1 と 5 の間に辺が張られます。3 を出力します。
  • 8 番目のクエリについて、頂点 2 と 5 は連結であるため、Yes を出力します。
  • 9 番目のクエリについて、連結成分は 1 つであるため -1 を出力します。
  • 10 番目のクエリについて、座標 (2,2) に頂点 6 を追加します。
  • 11 番目のクエリについて、連結成分は 2 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace です。異なる連結成分間の距離の最小値は 0 であり、頂点 4 と 6 の間に辺が張られます。0 を出力します。

Score : 500 points

Problem Statement

There is a graph G with N vertices and 0 edges on a 2-dimensional plane. The vertices are numbered from 1 to N, and vertex i is located at coordinates (x_i,y_i).

For vertices u and v of G, the distance d(u,v) between u and v is defined as the Manhattan distance d(u,v)=|x_u-x_v|+|y_u-y_v|.

Also, for two connected components A and B of G, let V(A) and V(B) be the vertex sets of A and B, respectively. The distance d(A,B) between A and B is defined as d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

Process Q queries as described below. Each query is one of the following three types:

  • 1 a b : Let n be the number of vertices in G. Add vertex n+1 to G with coordinates (x_{n+1},y_{n+1})=(a,b).
  • 2 : Let n be the number of vertices in G and m be the number of connected components.
    • If m=1, output -1.
    • If m\geq 2, merge all connected components with the minimum distance and output the value of that minimum distance. Formally, let the connected components of G be A_1,A_2,\ldots,A_m and let \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j). For all pairs of vertices (u,v)\ (1\leq u\lt v\leq n) that are not in the same connected component and satisfy d(u,v)=k, add an edge between vertices u and v. Then, output k.
  • 3 u v : If vertices u and v are in the same connected component, output Yes; otherwise, output No.

Constraints

  • 2\leq N\leq 1500
  • 1\leq Q\leq 1500
  • 0\leq x_i,y_i\leq 10^9
  • For queries of type 1, 0\leq a,b\leq 10^9.
  • For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i is the i-th query to be processed.

N Q
x_1 y_1
x_2 y_2
\vdots
x_N y_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following three formats:

1 a b

2

3 u v

Output

Output the answers to the queries separated by newlines, following the instructions in the problem statement.

Sample Input 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

Sample Output 1

No
1
Yes
2
No
3
Yes
-1
0

Initially, vertices 1,2,3,4 are located at coordinates (3,4),(3,3),(7,3),(2,2), respectively.

  • For the 1st query, vertices 1 and 2 are not connected, so output No.
  • For the 2nd query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace. The minimum distance between different connected components is 1, and an edge is added between vertices 1 and 2. Output 1.
  • For the 3rd query, vertices 1 and 2 are connected, so output Yes.
  • For the 4th query, add vertex 5 at coordinates (6,4).
  • For the 5th query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace. The minimum distance between different connected components is 2, and edges are added between vertices 2 and 4 and between vertices 3 and 5. Output 2.
  • For the 6th query, vertices 2 and 5 are not connected, so output No.
  • For the 7th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace. The minimum distance between different connected components is 3, and an edge is added between vertices 1 and 5. Output 3.
  • For the 8th query, vertices 2 and 5 are connected, so output Yes.
  • For the 9th query, there is 1 connected component, so output -1.
  • For the 10th query, add vertex 6 at coordinates (2,2).
  • For the 11th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace. The minimum distance between different connected components is 0, and an edge is added between vertices 4 and 6. Output 0.