OJ Board

any hint ?? I don't understand , How to solve it ?

Basic algorithm is breadth-first search.
You can use some data structure (linked list, or segments tree) to improve it, so that its overall running time will depend on the number of forbidden pairs or intervals, instead of the total number of edges.

mf wrote:Basic algorithm is breadth-first search.
You can use some data structure (linked list, or segments tree) to improve it, so that its overall running time will depend on the number of forbidden pairs or intervals, instead of the total number of edges.

yes, I think in that, but a don't know how to save, because in the breadth-first search i need to mark some position. :S the worse case is when i have a line and i can visit 41,000 / 2 nodes

I haven't got accepted. But I can give you some ideas. Suppose you have designed the edges in the linked fashion.

[0] -> (1 - 100) -> (500 - 1000) -> NULL
[1] -> (600 - 900) -> (950-1000) -> NULL

When searching from 0 you have visited 1 - 100 and 500 - 1000. Now when searching from 1 you don't need to visit again.

So, try to figure out a structure such that you can find large visited intervals in almost constant time.

EDIT : Got Accepted.

lord_burgos wrote:yes, I think in that, but a don't know how to save, because in the breadth-first search i need to mark some position.

Keep a linked list of unvisited nodes.
When you expand a node during breadth-first search, scan this list and erase all nodes from it, except those in forbidden intervals.

Total runtime of the algorithm would be proportional to number of forbidden pairs.

The worse case is when i have a line and i can visit 41,000 / 2 nodes

So what?

Anyway, worst-case input in the form of a line consists of just about sqrt(5000000) < 2300 vertices.

Hello,

there exists a solution in almost O(n+k).

Cu, Erik

Erik wrote:Hello,

there exists a solution in almost O(n+k).

Cu, Erik

Found Thanks.