Auto comment: topic has been updated by Seferoglu (previous revision, new revision, compare).

Auto comment: topic has been updated by Seferoglu (previous revision, new revision, compare).

You mean you changed ids to set? There is no nds in the Node struct

Auto comment: topic has been updated by Seferoglu (previous revision, new revision, compare).

I think the issue is the large global vectors of size N. Replacing these vectors with arrays makes the compile time go from 10s to 2s on my machine

Your code goes in an infinite loop because it has undefined behaviour. The message

Error: attempt to dereference a past-the-end iterator.

says that you are trying to dereference an iterator that does not have a value.
For example, auto temp = set.end(); auto x = *temp;. It is being caught by glibcxx's debug implementation of std::set.
See: std::set::end().

As for the high compilation times, they are certainly not due to the large sizes of the global vectors. The size of a vector does not effect compilation at all. It's quite the opposite, large global arrays effect compilation time since they are stored in the program image. I suspect the reason compilation times improve with arrays is due to the large number of vector operations you use which reduce to primitive array operations. For example, the function call std::vector<Node, std::allocator<Node>>::operator[]() reduces to a primitive array indexing operation.

That's insane :p

Long compilation time issue

I managed to reduce the long compilation issue to this program:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 1e5 + 1;
vector<string> strs(N), rev(N);
vector<pair<string, string>> qs(N);

int main() {
    // Fake work
    cout << strs.capacity() << ' ' << rev.capacity() << ' ' << qs.capacity() << '\n';
}

Here are some compilation time benchmarks on my local system with gcc (GCC) 14.2.1 20250405.

Benchmark 1: g++ -O2 -std=c++17 B.cpp
  Time (mean ± σ):     291.7 ms ±   2.5 ms    [User: 247.4 ms, System: 42.2 ms]
  Range (min … max):   289.0 ms … 297.3 ms    10 runs

Benchmark 1: g++ -std=c++20 B.cpp
  Time (mean ± σ):      7.023 s ±  0.036 s    [User: 6.693 s, System: 0.309 s]
  Range (min … max):    6.986 s …  7.082 s    10 runs

Benchmark 1: g++ -O2 -std=c++20 B.cpp
  Time (mean ± σ):      7.015 s ±  0.057 s    [User: 6.698 s, System: 0.300 s]
  Range (min … max):    6.964 s …  7.129 s    10 runs

An easy fix is to initialize the vectors with length N at runtime, like:

vector<string> strs, rev;
vector<pair<string, string>> qs;
vi ans;

void init() {
    strs.resize(N);
    rev.resize(N);
    qs.resize(N);
    ans.resize(N);
}

int main() {
    init();
    ...
}

The compilation time for your solution goes from 9.314s to 2.056s in C++20, and from 1.377s to 1.275s in C++17, after using the init function.

I tested on Compiler Explorer and for x86-64, gcc 14.2 takes approx 18s, while every version >= 14.3 takes approx 4s. So it is definitely a gcc bug, and the OJ is using a version <= 14.2.

set, in place of vector, causes infinite loop

The offending part is:

        for (auto id : nds[it].ids) {
            if (nds[node].trieroot == -1) {
                nds[node].trieroot = newnode();
            }
            ...
        }

You have two such loops where nds.push_back is called, via newnode(), while iterating over some field of some element of nds. When nds.push_back is called, the internal buffer might be reallocated and moved to some other memory address if the nds.capacity() == nds.size(). This means the nds[it] that you are working might be freed.

Again, here is a minimal reproduction of the issue:

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> nodes(1); // 1
    // vector<set<int>> nodes(1); // 2

    nodes[0] = {0, 1, 2};
    assert(nodes.capacity() == 1);
    auto* p = addressof(nodes[0]);

    for (auto id : nodes[0]) {
        if (nodes.size() == 1) {
            nodes.push_back({});
            assert(nodes.capacity() == 2);
        }

        auto* q = addressof(nodes[0]);
        cout << p->size() << ' ' << q->size() << ' ' << id << '\n';
        assert(p != q);
    }
}

You can comment out the vector line, and uncomment set one, to see the issue. Memory is invalidated in both the cases but my guess is that the range based for loop over a vector stores the size of the vector at the beginning, but range for loop over a set cannot do that so it must iterate till the iterator equals set::end().

As for long compile time for the C++20, I've done some research and turns out it's not a bug. Since C++20 there were introduced Constant initialization for all static storage duration variables, global vectors do have a static storage duration. Constant initialization is usually applied at compile time, so it probably increasing compile time for the big global vectors. If you set smaller value to the N, like 1000, Compile time will significantly be decreased.

As for global arrays getting compiled faster, it's obvious because they usually are way faster in initialization part than vectors, and doesn't allocate extra memory for later new elements.