洛谷编译时间太长会导致编译失败？

· · 个人记录

前几天做洛谷 P1144 最短路计数 时，意外发现一个奇怪的 BUG：提交后会提示“编译失败”，但是不给出任何编译失败的原因。这里给出一个编译失败链接

这次编译失败提交的代码如下：

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

const size_t MAXN = 1e6 + 10;
const unsigned INF = 1u << 31;

struct Edge {
    size_t to;
    unsigned cnt = 1; // Count how many path between two vertices
    Edge *next;
};

struct Node {
    Edge *first = nullptr;
    unsigned dis = INF;
    int 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;
            }
            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;
}

注意我的码风看起来和主流 OI 码风并不一致，我会使用结构体（类）和结构体指针，而不是开很多个数组。结构体的一个优点就是可以指定初始值，它在编译时会转化成该类的一个构造函数。以下函数构造 Node 类时，会指定属性 dis 的初始值为 INF：

const unsigned INF = 1u << 31;
struct Node {
    Edge *first = nullptr;
    unsigned dis = INF;
    int cnt = 0;
} nodes[1000010];

经过排查，我确认当上式中指定 dis = INF 时，本地编译时间会变长（需要大约 6 秒），而在洛谷上也会提示编译失败。但是，如果去掉 dis 的初始值指定，则编译时间大大缩短，洛谷上编译也能通过（这时候是 WA 而不是 CE）。

因此，可以肯定，结构体指定特殊的初始值会拉长编译时间，从而导致洛谷上编译超时。在一位汇编大佬的帮助下，我们总结出了编译时间拉长的原因：

对于 C++ 结构体而言，如果所有属性的初始值都指定，则编译器会将其优化，将所有初始值全部塞进程序中（是的，所有！这里一共塞了 16 * 1000010 字节的初始值，编译出来的文件接近 16 MB！）。

而如果有部分初始值未指定，例如上面的代码改成

const unsigned INF = 1u << 31;
struct Node {
    Edge *first = nullptr;
    unsigned dis = INF;
    int cnt;
} nodes[1000010];

则编译器会将这段代码优化成循环赋值，而不在编译过程写死初始值。这样编译出来的文件只有几百 KB。