ACPC 2017 - Lane Switching

Author: Benjamin Qi

Table of Contents

Edit on Github

Time Complexity:

Similar to the previous two problems in this module, we can binary search on the answer. However, there's a bit more implementation involved because we need to construct the graph first. Each vertex in the graph corresponds to a range of unoccupied space in a lane, and we draw an edge between two vertices with weight equal to the length of their vertical intersection.

1int N,M,R;
2vpi todo[100], range[100];
3int ind = 0;
4array<int,3> st; // your car (starting position)
6vector<vi> label;
7vector<vpi> adj;
8vi col;
9vb vis;

Give Us Feedback on ACPC 2017 - Lane Switching!

Join the Discussion!

Feel free to voice your thoughts in the comments section.