Security Badge

This problem gives us a graph, where any edge is permissible by a given range of integers. It then asks how many distinct integers can pass from one node to another by any path.

It should be clear from the limit that brute forcing by evaluating each integer individually will be too slow, and the most work we'll be able to do is either L^2 or N^2 or N*L (+or - a log).

A first try might be to bfs, and store the maximum set of numbers which can reach a given node. The issue here is the termination condition. When we reach a node, we have to recurse, but then we can reach that node again with an expanded set of nodes via some other path, and have to re-recurse. This leads to an exponential runtime. There is no way to "wait until we have all the integers that can reach a node" because the graph may not have a topological sort.

Looking back at the limits, we see that though the integer range goes up to 10^9, since we only have 5000 edges, we can compress the range. We are guaranteed that there are only 10,000 "elementary intervals," that is, intervals such that the range will either entirely pass through any edge, or be entirely blocked. We can thus BFS once for each of these intervals and see if we can reach the appropriate node.

Total runtime is 10k * 5k, or plenty fast.

One caveat while writing the code: To avoid all sorts of fence post issues, it makes sense to evaluate all ranges NON-INCLUSIVELY and then explicitly evaluate the endpoints. Otherwise, you end up having to deal with overlapping ranges, which is a pain. Depending on implementation, however, this may end up just slightly too slow, in which case one will have to handle the edge cases. The easiest way to do this is to use separate start and end sets for each interval, and then process them. The size of the range goes until the next entry in EITHER the start or end array. This should approximately halve the runtime.

import java.awt.Point;
import java.util.*;
public class b {
	static Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		int n=in.nextInt(),l=in.nextInt(),b=in.nextInt(),s=in.nextInt()-1,d=in.nextInt()-1;
		ArrayList<HashMap<Integer,Point>>al=new ArrayList<>();
		for(int i=0;i<n;i++)al.add(new HashMap<Integer,Point>());
		for(int i=0;i<l;i++)al.get(in.nextInt()-1).put(in.nextInt()-1, new Point(in.nextInt(),in.nextInt()));
		TreeSet<Integer>ts=new TreeSet<>();
		for(HashMap<Integer,Point>i:al)for(int j:i.keySet()){
			ts.add(i.get(j).x);
			ts.add(i.get(j).y);
		}
		int ans=0;
		//do it for ranges, non-inclusive
		while(ts.size()>1) {
			int on=ts.pollFirst()+1;
			Queue<Integer>q=new LinkedList<>();
			q.offer(s);
			boolean[] visited=new boolean[n];
			visited[s]=true;
			while(!q.isEmpty()&&!visited[d]) {
				int next=q.poll();
				for(int i:al.get(next).keySet()) if(!visited[i]&&al.get(next).get(i).x<=on&&al.get(next).get(i).y>=ts.first()-1){
					visited[i]=true;
					q.offer(i);
				}
			}
			if(visited[d])ans+=ts.first()-on;
		}
		//do it again for endpoints
		for(HashMap<Integer,Point>i:al)for(int j:i.keySet()){
			ts.add(i.get(j).x);
			ts.add(i.get(j).y);
		}
		while(ts.size()>0) {
			int on=ts.pollFirst();
			Queue<Integer>q=new LinkedList<>();
			q.offer(s);
			boolean[] visited=new boolean[n];
			visited[s]=true;
			while(!q.isEmpty()&&!visited[d]) {
				int next=q.poll();
				for(int i:al.get(next).keySet()) if(!visited[i]&&al.get(next).get(i).x<=on&&al.get(next).get(i).y>=on){
					visited[i]=true;
					q.offer(i);
				}
			}
			if(visited[d])ans+=1;
		}
		System.out.println(ans);
	}
}