/ Randle / 题库 /

玩游戏(CQ直辖市noip模拟赛联考) T2

玩游戏(CQ直辖市noip模拟赛联考) T2

【问题描述】
小 A 得了忧郁综合症,小 B 正在想办法开导她。
机智的小 B 决定陪着小 A 玩游戏,他从魔法的世界里变出一张无向联通图,
每条边上都有边权。小 B 定义一条路径的权值为所有经过边中的最大权值,小 A
则定义两点的最短路径为所有路径中权值最小的路径权。
每次小 A 先选出两个点 m1,m2,然后小 B 选出两个点 b1,b2,计算出它们的
最短路径 m,b,然后小 B 会拿出两堆灵魂宝石,一堆有 m 个,另一堆有 b 个。
然后小 A 先从一堆中选出若干个灵魂宝石拿走,接下来小 B 重复同样的操作,
如此反复,直到取走最后一颗灵魂宝石,然后取走最后一颗宝石的人获胜。
小 B 认为这样游戏太简单,于是他会不定期向这张图上加上一些边,以增
大游戏难度。
小 A 具有预知未来的能力,她看到了自己和小 B 在未来游戏中的选择,以
及小 B 增加的边。现在对于每次游戏,小 A 想知道自己是否存在必胜的方法。
但是预知未来已经消耗了她太多精力,出于疲惫她只好找到了你。

【输入格式】
第一行n与m,表示点数与边数。
接下来m行,每行u,v,l,表示u与v之间有一条权值为l的边。
接下来一个q,表示q组询问。
接下来q行两种操作
1:add u v l表示加一条从u到v的边权为l的点
2:game m1 m2 b1 b2表示小A和小B分别选择的起点和终点
数据保证连的边是没有自环的。

【输出格式】
对于每一次game询问,输出一行。如果小A有必胜方法输出“madoka”,否则输出“Baozika”,注意大小写哦。(我也不懂这是什么语言)

【样例输入】
5 6
1 2 3
2 3 6
4 2 4
5 3 5
3 4 5
5 1 5
4
game 1 3 4 3
game 1 5 2 4
add 2 5 4
game 1 5 3 4

【样例输出】
Baozika
madoka
madoka

【样例说明】
没有添加边前的两次游戏,分别是5,5和5,4
添加了一条边后的那次游戏,是4,5

【限制】
3秒钟(介于vijos评测机速度太快,应该比正常多一个点左右)
边权开longlong
对于30%3000次询问
对于60%100000次询问
对于100%150000次查询,其中add操作最多5000次

信息

难度
8
分类
(无)
标签
(无)
递交数
24
已通过
3
通过率
12%
上传者