编译时间太长会导致编译失败?
查看原帖
编译时间太长会导致编译失败?
733279
Sunlight_zero楼主2023/2/27 14:53

最近做 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)1000010 \times (8 + 4 + 4) 字节的初始值全塞进去,编译出来的 exe 接近 16 MB。这个优化是在编译过程进行的(即使不开 O2 也有这个优化),会导致编译时间相比正常程序较长。个人推测因为编译时间较长,洛谷的 OJ 判定为编译失败了。

又经过测试,如果只初始化 10510^5 个结构体,这段代码不会导致编译失败,但 10610^6 就编译失败了。另外,如果只指定其中部分属性的初始值,例如

struct Node {
    Edge *first = nullptr;
    unsigned int dis = INF, cnt;
} nodes[MAXN];

以上代码 cnt 的初始值没有指定,则编译器会优化为循环,而不会将初始值全塞进程序,编译过程也很快,不会超时。

建议提高一下编译时间的阈值?指定结构体初始值并不算不常见的行为。

2023/2/27 14:53
加载中...