Problem 3425 --韭菜国的大选

3425: 韭菜国的大选

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $8$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
韭菜国的大选年到了,韭菜国议会将要选举出新的执政党。议会的选举制度是这样的:最一开始的时候每位议员都会各自组建独立党派,每个党派之间可以派出一位代表进行一对一谈判,如果谈判成功,那么两位议员分属的不同党派将合并成一个新的党派。最后包含议员数量最多的党派将获胜。作为韭约时报的记者,你将全程报道大选的过程。每一次的一对一谈判将是你报道的重点,此外,你还需要回复你热情的观众:选民们有时会对一些高人气的议员的活动很感兴趣,比如某两位议员现在是否属于同一党派,如果是,那么他们是什么时候成为同一阵营的。现在只考虑成功的谈判,并把每一次成功的谈判和观众的提问都视为一次事件,在大选中有若干次事件发生,对每次提问的事件,你都需要进行回答。
第一行两个正整数 n和 m,分别表示韭菜国议会有 n 名议员,选举中发生了 m个事件。保证 n<=3*10^5, m <= 3 * 10^5。
接下来 m 行,每行一个字符串 s 和两个整数 a, b。保证 1<=a,b<=n。
如果 s的内容为`join`,则意味着本次事件是 a和 b 两位议员成功进行了谈判。
如果 s 的内容为`query`,则意味着你需要回答当前 a 和 b两位议员是否属于同一党派。
对于每一次询问的事件,你都需要进行回答,每次回答占一行,如果两位议员不是同一阵营,输出NO;反之输出YES和一个数字 $i$,表示是在第 $i$ 次事件中两位议员成为了同一阵营。
5 8
join 1 3
query 2 5
join 3 5
join 1 4
query 1 5
query 4 3
join 2 4
query 2 5
NO
YES 3
YES 4
YES 7

推荐代码 查看3425 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 滁院の亚托克文 613372 2020-09-28 20:57:09
内存最少[$4428 $KB] fancy 742793 2021-04-22 22:12:38
第一AC AOJ大管家 613354 2020-09-28 19:06:14
第一挑战 AOJ大管家 613354 2020-09-28 19:06:14

赛题来源/所属竞赛 2020安徽省ACM赛9月月赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1539 2020安徽省ACM赛9月月赛 2020-09-27 13:00:00 请登录