将 bool mp[N*N] 改为 unordered_map<int, bool> mp 后出现 Aborted(程序异常终止),核心原因是 时间效率不足导致超时,具体分析如下:

  1. 数据规模与操作复杂度对比 全局数组 mp[NN]: N=3005 时,NN≈9e6,数组大小为 9030025(3005×3005)。数组访问是 O (1) 时间,且内存连续,速度极快。 unordered_map<int, bool>: 哈希表的插入、查询操作平均时间是 O (1),但实际受 哈希冲突 和 动态内存管理 影响: 每次操作需要计算哈希值(如 hax(bel[v], bel[u])),并处理冲突链; 动态分配内存的 overhead 更高,频繁操作时耗时显著增加。
  2. 代码中的操作规模 在处理分量间边时,最坏情况(原图为完全图) 会遍历 N²≈9e6 条边。此时:

数组 mp 的访问是 9e6 次 O (1) 操作,耗时可忽略; unordered_map 的 9e6 次插入 / 查询 会因哈希计算、冲突处理和内存操作,导致总时间急剧上升,超过时间限制,最终被系统终止(Aborted)。 3. 解决方案 若需优化空间(如 N 更大时),可改用 bitset 或更紧凑的哈希结构,但在本题数据规模下:

优先保留全局数组 mp[N*N]:其时间效率最优,且 9e6 大小的 bool 数组仅占~9MB 内存(全局数组存放在数据段,空间充足)。

综上,unordered_map 的时间开销在大数据量下无法满足要求,导致程序超时终止。建议继续使用全局数组实现快速存在性判断。

0 条评论

目前还没有评论...

信息

ID
345
时间
1000ms
内存
256MiB
难度
8
标签
(无)
递交数
83
已通过
14
上传者