Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

tautology's blog

By tautology, history, 4 weeks ago, In English,

Given a unweighted, undirected graph of N vertices and M edges, vertices are numbered from 1 to N. Also there are K special vertices. You have to answer Q queries. In each query, you're given a vertex V. You have to print shortest distance of nearest special vertex. If there is no special vertex reachable from V, print -1.
Note : Graph doesn't contain multiple edges or self loops and it may be disconnected.
Constraints :
1 <= N, K, Q <= 1e5
1 <= M <= 2e6
Sample Input:
5 3 3 // N M K
1 2 // edge 1
2 3 // edge 2
1 3 // edge 3
1 3 5 // special vertices
5 // Q
1 // V for 1st query
2 // " " " 2nd " "
3 // " " " 3rd " "
4 // " " " 4th " "
5 // " " " 5th " "

Sample Output:
0
1
0
-1
0

P.S. : This problem was asked in Codechef's CCDSAP advanced contest on 22th Sept.,2019. Now it's over.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

You can use BFS.

But at first add all the special nodes to queue and set the distances of special nodes 0 and then run the BFS. And calculate the distance of each node in that way.

Then you can answer each query in O(1).

Sorry for my bad English.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wont that time out given K, M, N are order of 1e5 ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No. The idea is to perform a multisource BFS. You first place all the special vertices in a queue and afterwards you run a normal BFS. Then, you will have a dist array with the shortest path from a given node to the nearest special node. Since you only run BFS once, the complexity will be O(V + E). All queries will be answered in O(1)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dude, that was private contest and It was clearly mentioned not to discuss problem on public platforms, even after contest. Don't disrespect their policy.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fu*k off! What people suppose to do when they don't get the solution or editorial ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @1600 Bro the ultimate aim is to learn..so pls if u cant help atleast dont stop others