[BZOJ 4195]程序自动分析

看起来是道并查集水题……

可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?

注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!

这种技术,就是离散化

同时注意防卡常!

代码:

继续阅读

[BZOJ 4196]软件包管理器

终于A了!

在CodeVS,洛谷甚至UOJ上各种A

但是在BZOJ上各种TLE。BZOJ评测姬自带10倍常数?

这题处理安装很简单,一直溯到根。

删除……注意一下树剖的一些神奇性质。

继续阅读