Toll Gates
Problem Statement
Solution
Important definitions
- Let there be a directed graph such that:
- .
- A path on this graph is defined as a sequence of edges such that:
- for
- and either or .
- We define a path between and to be any such path where and , such that is the number of edges in the path.
- We define to be the first edges of the path.
- We define as the score of an edge between , where if and if (it is not defined otherwise). The former are referred to as "positive" edges, the latter as "negative" edges.
- We define the score of a path to be the sum of the scores of all its edges.
You are given pairs such that . Your goal is to determine, for each given instance of , if there exists a path between each and such that and .
Subtask 1: is a path graph,
One can observe that there is a forced path that has to be taken to go from any to its corresponding . Any additional "detour" will not affect the score as it will have to be reversed. For example, in this graph, there is no way to go from to without having a final score of : there is the forced path , and trying to go to will not fix the score as the path has a score of .
The solution comes naturally: do a DFS/BFS from your only to your updating score and making sure the path is valid. If the traversal reaches and the score of the path is , then there is a valid path between and . Otherwise, there isn't. This takes time, which solves this subtask.
Subtask 2: is a rooted spider graph, all edges are oriented towards the root
Since a spider graph is a tree, there is still the same idea that between any two nodes, there is only one path. Additionally, notice two things:
- If two nodes are on the same row, then obviously one cannot reach the other, because they are only doors of the same color between them.
- Paths between two nodes of two different rows can be considered "unimodal", in the sense that the path is a sequence of blue doors then red doors.
We thus know that a node can reach the other if this sequence has the same amount of blue doors than red doors. Finally, we know that the amount of blue doors is the distance of the first node from the root, and the amount of red doors is the distance of the second node from the root. Consequently, to solve this subtask, you merely need to check if the distance of the two nodes from the root is equal.
This can be preprocessed with a BFS in time. Each query can be handled in time, which results in a final complexity of time.
Subtask 3: In any path over , . is connected.
I'll start by making a foundational observation to the cases in this subtask: if the score of every path always tends between and , this means that there is no way to see two edges of the same sign on any path. Notice how this means that a node is either connected only to positive edges or only to negative edges. Furthermore, notice that the graph is connected, so there is necessarily a path between any two nodes.
These two ideas combined allow us to make a bipartite coloring of the nodes of where the nodes in set only have positive edges, and the nodes in set only have negative edges. Naturally, no path can start at the nodes of because they will immediately cause a score of when reaching any adjacent edge. However, the nodes of can reach each other because the paths between them start at , go to when hitting any nodes in , and then back to when heading for an edge in . There is always a path of edges between each of the nodes of because the graph is connected. Thus, all nodes in can reach each other, andthe nodes in can't reach anything but themselves.
The coloring can be done in time by reading the input and assigning to the nodes with positive edges and to the nodes with negative edges. Answering each query can be done in time by checking if are in or . Final complexity is .
Subtask 4: is a path graph.
Building on the fact that a path graph is basically an array, we can quickly find the solution to this subtask: lay the nodes of along an array and then do an iteration starting from the first edge of to the last, assigning each node a value , which is the score resulting from a path starting at said first edge and ending at . We can thus observe that if , the path between them has a score of , which validates one of the conditions for checking that the path is valid.
However, there is another condition to verify, which is that the path does not have a negative score anywhere. To do this, we need to check that there exists no between and such that , because if that were the case, this would mean that there is such a path with negative score. To find such a , suffices to find the minimum of the score on the path between and . Notice how this is identical to the RMQ problem, which can be solved efficiently using a segment tree.
Constructing a segment tree takes time, and each query on a segment tree takes time. Thus, the final complexity is time.
Subtask 5: is a tree
Fundamentally, the same ideas hold from the previous subtask, except some changes have to be made: instead of calculating from the first node, we can just simply take any node as the root of the tree, and calculate relative to it. We still check if .
What is different this time around is that we need to answer the RMQ problem on trees now instead of arrays, and that requires a different technique; binary lifting: We check that, on paths and , there is no , and this by simply keeping track of the minimum up to the th ancestor for each node and applying binary lifting.
Considering that the amount of information tracked per node is at most with being the distance between the root and the lowest leaf ( in the worst case) we have to do at most calculations. Answering each query still takes time, so we end up with a final complexity of .
Subtask 6:
For this subtask, a drastic change in solving strategy has to occur for a functional solution. The reason for this being that we no longer have the guarantee that there is only one path between two nodes, which means that can't be fixed for all instances of the graph.
We will thus present a different way of solving the problem: if we know that there exists a where the graph has a path of score between and and a path of score between and , we know that there exists a solution between and . To find the existence of such a path, we will use dynamic programming, where there are three states , and each corresponding to paths of score , score and score .
The base case is that, for each node of our graph, , and if we have , we set and . We then solve by checking, for each state if there exists a such that and or and . We also propagate , to other nodes: we update states and for each .
Since there are states, and each state needs to check different values of , we have a final complexity of .
Full solution
How do we optimize the solution even further? One more observation can be made: if there is a path between and , the inverse path is also valid, thus there is a path between and . This also means that whatever score is obtainable in can also be obtained in . We can thus treat and as the same node. In technical terms, we simply merge nodes and whenever we find a valid path between them, which is whenever and are both adjacent to the same node/cluster of nodes.
Merging can be done using a Union-find data structure in time, where is the inverse ackermann function. Queries can also be answered in time, which results in a final time complexity of time, solving our problem under the given constraints.
Here is a sample implementation:
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
void make_set(vi &par, vi &size, int node){
par[node] = node;
size[node] = 1;
}
int find_set(vi &par, int node){
if(node == par[node]) return node;
return par[node] = find_set(par, par[node]);
}
void union_set(vi &par, vi &size, int u, int v){
int pu = find_set(par, u), pv = find_set(par, v);
if(pu == pv) return;
if(size[pu] >= size[pv]){
par[pv] = pu;
size[pu] += size[pv];
}
else{
par[pu] = pv;
size[pv] += size[pu];
}
}
int main()
{
int n, m, q;
cin >> n >> m;
vector<vi> adj(n+1);
vi p(n+1, 0), sz(n+1, 0);
queue<int> dsq;
int a, b;
for(int i = 1; i <= n; ++i) make_set(p, sz, i);
for(int i = 0; i < m; ++i){
char c;
cin >> a >> b >> c;
if(c == 'B'){
adj[b].push_back(a);
if(adj[b].size() == 2) dsq.push(b);
}
else{
adj[a].push_back(b);
if(adj[a].size() == 2) dsq.push(a);
}
}
while(!dsq.empty()){
int u = dsq.front();
dsq.pop();
set<int> ele;
for(auto i : adj[u]) ele.insert(find_set(p, i));
int x = *(ele.begin());
if(ele.size() > 1){
if(x == u) x = *(ele.begin()++);
for(auto i : ele){
union_set(p, sz, x, i);
if(find_set(p, x) == i) swap(x, i);
if(i == x) continue;
if(i == u) adj[x].push_back(x);
else{
for(auto e : adj[i]) adj[x].push_back(e);
adj[i].clear();
}
}
if(adj[x].size() > 1) dsq.push(x);
}
if(ele.find(u) == ele.end() || ele.size() == 1){
adj[u].clear();
adj[u].push_back(x);
}
}
cin >> q;
for(int i = 0; i < q; ++i){
cin >> a >> b;
if(find_set(p, a) == find_set(p, b)) cout << "1\n";
else cout << "0\n";
}
return 0;
}