F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4683. -- 动态仙人图

4683: 动态仙人图

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 39  Solved: 21
[Submit][Status][Discuss]

Description

背景
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掉这道题
可是他完全不会做
于是来求助你辣!

Input

第一行n,m表示有n个节点,m个操作
接下来m行,每行一个操作
保证必定为link cut或者distance?
m <= 300000,所有关于边长的计算在int范围内

n <= 100000

有可能有重边(有可能权值一样的重边)
有可能link自环,此时输出failed
有可能询问两个相同的点的最短路,此时输出0

Output

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

Sample Input

样例输入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

Sample Output

样例输出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

HINT

Source

by AwD & HFLSyzx

[Submit][Status][Discuss]

HOME Back