← 返回题目列表

AtCoder · abc409_f

I. 连接点

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

分数: 500 点

问题陈述

有一张图 G 与 N 顶点和 0 边缘 2维度平面。顶点编号从 1 to N,和顶点 i 位于坐标处 (x_i,y_i).

对于顶点 u 和 v of G,距离 d(u,v) 之间 u 和 v 定义为曼哈顿距离 d(u,v)=|x_u-x_v|+|y_u-y_v|.

另外,对于两个连接的组件 A 和 B of G,让 V(A) 和 V(B) 是顶点集 分别为 A 和 B。距离 d(A,B) 之间 A 和 B 定义为 d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

流程 Q 查询如下所述。每个查询都是以下三种类型之一:

  • 1 a b :让 n 是顶点数 G。添加顶点 n+1 to G 坐标 (x_{n+1},y_{n+1})=(a,b).
  • 2 :让 n 是顶点数 G 和 m 是连接组件的数量。
    • If m=1,输出 -1.
    • If m\geq 2,合并所有具有最小距离的连通分量并输出该最小距离的值。形式上,让连通分量 G be 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,让 n 是顶点数 G 在处理该查询之前,然后 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

每个查询均以以下三种格式之一给出:

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)。

  • 对于 1st 查询,顶点 1 和 2 未连接,因此输出 No.
  • 对于 2nd查询,有 4 连通分量,每个连通分量的顶点集是 \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace。不同连通分量之间的最小距离为 1,并在顶点之间添加一条边 1 和 2。输出 1.
  • 对于 3rd 查询,顶点 1 和 2 已连接,因此输出 Yes.
  • 对于 4第查询,添加顶点 5 位于坐标处 (6,4).
  • 对于 5第次查询,有 4 连通分量,每个连通分量的顶点集是 \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace。不同连通分量之间的最小距离为 2,并且在顶点之间添加边 2 和 4 和顶点之间 3 和 5。输出 2.
  • 对于 6th 查询,顶点 2 和 5 未连接,因此输出 No.
  • 对于 7第次查询,有 2 连通分量,每个连通分量的顶点集是 \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace。不同连通分量之间的最小距离为 3,并在顶点之间添加一条边 1 和 5。输出 3.
  • 对于 8th 查询,顶点 2 和 5 已连接,因此输出 Yes.
  • 对于 9第查询,有 1 连接组件,因此输出 -1.
  • 对于 10第查询,添加顶点 6 位于坐标处 (2,2).
  • 对于 11第次查询,有 2 连通分量,每个连通分量的顶点集是 \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace。不同连通分量之间的最小距离为 0,并在顶点之间添加一条边 4 和 6。输出 0.