DMOJ - Time Traveller Imaxblue

Process portals and queries in reverse order of time. Maintain a priority queue at each vertex. Whenever we see a portal, add to each of the portals along its centroid path.

Time Complexity: $\mathcal{O}((N+Q)\log N+M\log^2N)$

Memory Complexity: $\mathcal{O}((N+M)\log N+Q)$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;