Hey I think I'm using my mac's clang llvm compiler to compile my code with the following flags :

g++ -std=c++20 -DDEBUG -DYEET -fsanitize=address -fsanitize=undefined -fno-sanitize-recover=all -fsanitize=float-divide-by-zero -fsanitize=float-cast-overflow -fno-sanitize=null -fno-sanitize=alignment $$$filename -o $$${filename%.*}

and when I compiled the following code : 291228049 and ran it against any test case of the problem 1398D - Colored Rectangles, I got the following :

But as you can check out, the submission was accepted on Codeforces, which confuses me. How do I begin to understand what's going on?

Thanks for your help and let me know if you need any more information

Edit 1 : I tried to run with just the address sanitizer flag, and I still got a runtime error. Then I decided to remove all the sanitizers and I still got the error so I thought the "-DDEBUG" flag was the culprit and I was right :")

debug(dp) which was a 3-D std::array gave the error.

I'm still not sure why, but at least it's not a compiler issue, which would've been harder to debug, lol!

Thanks!

Motivation

MST, or Minimum Spanning Tree, is an acyclic subgraph of a graph, where the total weight of its edges is minimal. Their properties are often used in problems with edge-weighted graphs. But what about node-weighted graphs? A problem structured on edges can often be modified to one based on nodes. In such situations, data structures and algorithms analogous to those used for edges can be applied. Let's look at one such problem!

The Minimax problem

The minimax path problem involves finding the minimum of the maximum edge weights among all possible paths between two vertices, $$$i$$$ and $$$j$$$. And it turns out that, the minimax path always is a part of the MST!

Hence the solution involves finding the MST of the graph, and because trees only have one simple path between two vertices, either through DFS or through precomputation answering the query of $$$i$$$ $$$j$$$ in $$$O(n)$$$ or $$$O(\log(n))$$$ time.

Vertex Minimax problem

This is similar to the minimax problem, but instead of minimizing the maximum weighted edge along all paths, this deals in minimizing the maximum weighted node along all paths between two vertices. Let's see how our node analogy for MST deals this problem for us!

The Algorithm

In the original problem, we constructed a tree that had filtered out all the non-optimal paths between every pair of vertices leaving only the ones we want. Let's try to recreate the same! In our case "optimal" path would be one whose heaviest node is minimized.

Multiple paths between two vertices arise in the presence of cycles. So making a tree from a graph comes down to choosing which edge to cut in each cycle, hence let's observe a cycle in detail.

The Strategy

In a cycle, there are two simple paths between each pair of vertices and out of the two, the one with the heavier maximum weighted node, will always pass through the heaviest node in the cycle. Hence, we must cut any one of the two edges connected to the heaviest node in each cycle!

#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
vpii vertexMST(vpii edges, vi weight){
        int m = edges.size();
        int n = weight.size();
        //add v,u for all u,v in the list
        for(int i=0;i<m;i++){
                edges.pb({edges[i].second,edges[i].first});
        }
        //sort based on weight of first vertex
        sort(edges.begin(),edges.end(),[&](pii a,pii b){
                return weight[a.first] < weight[b.first];
        });

        vpii new_edges;
        vi vis(n,0);
        for(auto it:edges){
                int u = it.first;
                int v = it.second;
                //if we haven't added vertex u to our tree/forest yet then add it
                if(!vis[u])
                        vis[u] = 1;
                //if adding vertex v doesn't create a cycle and v is in our tree/forest then add it
                if(dsu.find(u) != dsu.find(v) and vis[v]){
                        new_edges.pb({u,v});
                        dsu.merge(u,v);
                }
        }
        return new_edges;
}

1851G - Vlad and the Mountains

I would urge you to try to solve it assuming the queries are online and relate to what we have learnt.

Here is my submission link for reference : 217042760

Note

The editorial's solution involves offline queries, do check that out too!

Conclusion

I don't know if this was common knowledge and couldn't find anything like it in my limited search on the net, but seemed like an interesting find :)

Please let me know if there are other problems that can be solved using this, I will link them in the blog!

UPD — 1

vgtcross mentions an elegant alternative approach in the following comment. This also aids in the understanding of the algorithm for vertex MST as the rules of adding an edge when seen through the lens of this approach makes the algorithm identical to the kruskal's algorithm for MST!