最近做 P1144 的时候,提交了一段代码,反复提示编译失败(不只是 CE,编译失败且没有给出任何错误提示),编译失败链接
代码如下:
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
const size_t MAXN = 1e6 + 10;
const unsigned int INF = (1u << 31) - 1;
struct Edge {
size_t to;
unsigned cnt = 1; // Count how many path between two vertices
Edge *next;
};
struct Node {
Edge *first = nullptr;
unsigned int dis = INF, cnt = 0;
} nodes[MAXN];
unordered_map<size_t, Edge*> f;
void create_edge(size_t u, size_t v)
{
Edge *e = f[u * MAXN + v];
if (e)
{
e->cnt++;
f[v * MAXN + u]->cnt++;
}
else
{
Edge *e = new Edge;
e->next = nodes[u].first;
e->to = v;
nodes[u].first = e;
f[u * MAXN + v] = e;
e = new Edge;
e->next = nodes[v].first;
e->to = u;
nodes[v].first = e;
f[v * MAXN + u] = e;
}
}
queue<size_t> qu;
bool visited[MAXN];
void dijkstra(size_t s)
{
nodes[s].dis = 0;
nodes[s].cnt = 1;
qu.push(s);
while (!qu.empty())
{
size_t u = qu.front();
qu.pop();
if (visited[u])
{
continue;
}
visited[u] = true;
for (Edge *e = nodes[u].first; e != nullptr; e = e->next)
{
size_t v = e->to;
if (nodes[u].dis + 1 < nodes[v].dis)
{
nodes[v].dis = nodes[u].dis + 1;
nodes[v].cnt = nodes[u].cnt * e->cnt % 100003;
}
else if (nodes[u].dis + 1 == nodes[v].dis)
{
nodes[v].cnt = (nodes[v].cnt + nodes[u].cnt * e->cnt) % 100003;
}
qu.push(v);
}
}
}
int main()
{
ios::sync_with_stdio(false);
size_t n, m, s = 1, u, v;
cin >> n >> m;
while (m--)
{
cin >> u >> v;
create_edge(u, v);
}
dijkstra(s);
for (size_t u = 1; u <= n; u++)
{
cout << nodes[u].cnt << "\n";
}
return 0;
}
本地调试发现这段代码的编译时间确实偏长,经过“二分查找”确定编译时间最长的地方位于结构体 Node:
struct Node {
Edge *first = nullptr;
unsigned int dis = INF, cnt = 0;
} nodes[MAXN];
经过一个汇编大佬的指导,发现当结构体的所有属性都指定初始值时,编译器会将所有的初始值都塞进程序里。比如这里初始化了 1000010 个 Node 结构体,编译器把 1000010×(8+4+4) 字节的初始值全塞进去,编译出来的 exe 接近 16 MB。这个优化是在编译过程进行的(即使不开 O2 也有这个优化),会导致编译时间相比正常程序较长。个人推测因为编译时间较长,洛谷的 OJ 判定为编译失败了。
又经过测试,如果只初始化 105 个结构体,这段代码不会导致编译失败,但 106 就编译失败了。另外,如果只指定其中部分属性的初始值,例如
struct Node {
Edge *first = nullptr;
unsigned int dis = INF, cnt;
} nodes[MAXN];
以上代码 cnt 的初始值没有指定,则编译器会优化为循环,而不会将初始值全塞进程序,编译过程也很快,不会超时。
建议提高一下编译时间的阈值?指定结构体初始值并不算不常见的行为。