8683: BZOJ4683:动态仙人图
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
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掉这道题 可是他完全不会做 于是来求助你辣!
输入格式
第一行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
提示
没有写明提示
题目来源
by AwD & HFLSyzx