#1655. 「CERC2018」The Bridge on the River Kawaii

    ID: 1655 传统题 5000ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>并查集图论离线分块及按大小分类分治2018ICPC

「CERC2018」The Bridge on the River Kawaii

题目描述

译自 CERC 2018B. The Bridge on the River Kawaii

在一个遥远的,叫做 Midsommer 的地方,有一条叫做 delta 的小河。河里流的是深紫色的酸,所以不可能在那里游泳。这条河周围有一些小岛,并且有桥连接它们。每座桥都有一个危险系数,表示通过这座桥有多危险。危险系数越高,通过这座桥就越危险。

一位叫做 Richard Hradecki 的侦探兼悬疑小说作家经常需要通过这些桥来追查案件。在所有可能的路径中,他更倾向于选择最安全的一条,也就是这条路径上经过桥的最大危险系数越低越好。

为了规划路线,Richard 经常让你为他找从一个岛到他要调查的岛的最安全路线。为了满足他的需求,你需要连续处理以下三种事件:

  • 当地人在两座岛屿之间建了一座新桥;
  • 一只酸性的并且毛茸茸的大粉熊 Lug 出现了,并摧毁了一座桥;
  • Richard 要求你找两个岛屿之间的最安全路线。

输入格式

第一行包含两个整数 N,QN,QNN 是岛屿数(岛屿用 0N10\ldots N-1 标号),QQ 是需要处理的事件数。

接下来 QQ 行,每行表示一个事件,包含三或四个整数,说明如下:

  • 0 X Y V0\ X\ Y\ V:在 XX 岛与 YY 岛之间刚建成一座危险系数为 VV 的桥;
  • 1 X Y1\ X\ Y:连接 X,YX,Y 两岛的桥刚被摧毁;
  • 2 X Y2\ X \ Y:Richard 询问从 XXYY 的最安全路径。

对于所有类型的询问,X,YX,Y 表示一对合法的岛屿。保证任意两个岛屿之间最多只存在一座直达的桥,要被摧毁的桥在那一刻是存在的。

输出格式

对于每个种类为 22 的事件,输出 XXYY 最安全路径上经过的最危险的桥的危险系数。如果 XXYY 之间没有路径,输出 1-1

样例 1

6 15
0 1 2 1
2 1 4
2 1 5
0 2 3 2
2 1 4
2 1 5
0 3 4 3
2 1 4
2 1 5
0 4 5 4
2 1 4
2 1 5
1 4 5
2 1 4
2 1 5
-1
-1
-1
-1
3
-1
3
4
3
-1
6 6
0 2 0 4
0 3 4 3
0 0 4 1
0 2 5 4
2 3 2
2 4 2
4
4

数据范围与提示

$2\le N\le 10^5,1\le Q\le 10^5,0\le V\lt 10,0\le X,Y\lt N,X\neq Y$