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

IX Zhautykov Olympiad : [Problem D] Special Graph

Revision en2, by Azret, 2015-12-23 11:28:37

Hello.

Given directed unweighted graph. It consist of N ≤ 105 vertices. There is at most one edge from each vertex. You need to answer for two types of queries (Q ≤ 105):

  1. Delete an edge from vertex V. Unexisting edge won't be deleted.
  2. Find shortest path from U to V.

No ideas. How to solve it?

Tags hard, special, izho, gold

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Azret 2015-12-23 11:28:37 6
en1 English Azret 2015-12-23 11:28:21 381 Initial revision (published)