logo AlgoBeat OnlineJudge
登录 注册

#104683. [BZOJ 4683] 动态仙人图

内存限制：256 MiB 时间限制：30000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

背景

AwD大爷是个神犇

题目

AwD大爷又单手屠了仙人掌辣

蒟蒻HFLSyzx在旁边跪地不起

AwD大爷觉得仙人掌实在是太没有挑战性了，于是便开始yy仙人掌的加强版——仙人图

定义仙人图为每条边至多在两个简单环上的图

现在初始仙人图是空的，你需要支持三个操作

link a b w

添加一条连接a,b的边，权值为w

如果添加完毕之后还是仙人图，输出ok

否则输出failed，并撤销本次操作

cut a b w

删除一条连接a,b权值为w的边

如果有多个删除一个

如果不存在这样的边输出failed，并忽略本次操作

否则输出ok

distance? a b

询问a,b之间的最短路

如果a,b不连通输出-1

AwD大爷造完题后一眼秒了，把题扔在一边

蒟蒻HFLSyzx看到后直接吓晕过去

为了不在AwD大爷面前丢脸，蒟蒻HFLSyzx必须A掉这道题

可是他完全不会做

于是来求助你辣！

输入格式

第一行n，m表示有n个节点，m个操作

接下来m行，每行一个操作

保证必定为link cut或者distance?

m <= 300000,所有关于边长的计算在int范围内

n <= 100000

有可能有重边（有可能权值一样的重边）

有可能link自环，此时输出failed

有可能询问两个相同的点的最短路，此时输出0

输出格式

对每个操作输出一行，代表该操作的结果/答案

样例

样例输入

样例输入1
5 12
link 1 2 3
link 2 3 3
distance? 1 3
cut 2 3 3
distance? 1 3
cut 2 3 2
link 2 3 2
cut 2 3 3
link 3 4 3
link 4 1 5
link 1 3 8
link 2 4 7

样例输入2
6 25
link 1 2 3
link 1 2 2
link 1 2 5
cut 1 2 2
cut 1 2 5
link 1 2 3
link 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
cut 1 2 3
link 1 2 4
link 1 3 5
distance? 2 3
link 2 4 1
link 3 4 2
link 2 3 3
link 1 4 7
link 1 4 7
cut 1 4 7
link 5 6 8
distance? 3 6
distance? 2 6
cut 2 4 1
distance? 1 5

样例输出

样例输出1
ok
ok
6
ok
-1
failed
ok
failed
ok
ok
ok
failed



样例输出2
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
failed
ok
ok
9
ok
ok
ok
failed
failed
failed
ok
-1
-1
ok
-1

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium