爆杀众多题解

P1983 [NOIP2013 普及组] 车站分级

Lagerent @ 2022-11-19 09:54:52

此题数据范围 n, m \le 1000

拓扑或者差分约束的想法，由没到达的车站向到了的车站连边

考虑构造最坏情况，即对于 1000 条路线，每 500 个节点向另外 500 个节点连边，那么总共的节点数会达到 500 * 500 * 1000 = 2.5 * 10^8，直接暴力建图时空可能都会爆炸。

许多题解暴力建图，无法通过此 hack 数据。

比如这篇题解和这篇题解的第一种做法

应该还有好多，HACK 数据在这里

请求添加数据 @chen_zhe @小粉兔

by Lagerent @ 2022-11-19 09:55:18

@chen_zhe @小粉兔

by Lagerent @ 2022-11-19 09:57:45

这篇题解也寄了

by Lagerent @ 2022-11-19 09:59:00

不好意思口误，是边数会达到 2.5 \times 10 ^ 8

by Lagerent @ 2022-11-19 10:02:40

还有这篇，排除防抄袭之后会T

by Lagerent @ 2022-11-19 10:05:31

@离散小波变换°

by Lagerent @ 2022-11-19 10:12:16

帖子中提到第一种做法寄了的题解，实际三种做法都寄了（

by Lagerent @ 2022-11-19 10:17:04

还有这篇

by chen_zhe @ 2022-11-19 11:01:31

@Lagerent 话说回来，如果线段树优化建图都寄了，那是不是可以理解为没有什么做法可以在当时的老爷机（AMD 速龙 64x2 Dual Core CPU 5200+）上跑过这个题（

by Lagerent @ 2022-11-19 11:27:07

@chen_zhe 建立中间虚拟节点建图能过啊qwq

by Lagerent @ 2022-11-19 11:31:50

@chen_zhe 可以把线段树复杂度的那个 log 给优化掉。

| 下一页