Mock CCO '17 Day 1 P3 - Connection

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.2s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The Amestris government has been alerted of imaxblue's plan, and has decided to shut down all bidirectional roads between its N+1 cities, numbered 0 to N. However, they are going to be slowly reopening roads, at a steady rate of 1 road per day, for days 0 to D-1. imaxblue knows their plan, and will only move between two cities if he knows that they are in the same strangely connected component. He will ask Q queries in the form "x\ y", asking the first day on which x and y will be strangely connected, or -1 if it will never be strangely connected.

Note: We define a strangely connected component as a connected component that will not be disconnected by removing any 1 edge.

Input Specification

First line: N, D, Q
Next D lines: 2 integers A_i and B_i, representing that cities A_i and B_i are connected on the i-th day.
Next Q lines: 2 integers x_i and y_i, representing a query.


For full points, N, D, Q \le 150\,000
For 5/25 points, N, D, Q \le 5\,000

Sample Input

4 5 3
3 3
1 3
3 0
3 2
2 3
0 2
3 3
0 3

Sample Output



  • 3
    wleung_bvg  commented on Aug. 9, 2018, 8:09 p.m.

    There appears to be test cases where a == N or b == N, despite the cities being numbered from 0 to N - 1.

    • 2
      Kirito  commented on July 23, 2020, 8:43 p.m.

      Corrected statement...

  • 2
    wleung_bvg  commented on March 28, 2018, 8:23 p.m. edited