Mock CCC '15 S5 - Kongou - DMOJ: Modern Online Judge

Mock CCC '15 S5 - Kongou

View as PDF

Submit solution

All submissions

Best submissions

Points: 40 (partial)

Time limit: 13.0s

Memory limit: 256M

Author:

FatalEagle

Problem types

2015 Mock CCC by Alex and Timothy

You are the admiral of an admirable fleet of battleships! Your flagship is the Kongou*, and you have never lost a single battle in your entire career. This is because you have adopted the foolproof strategy of blocking off all critical rivers before engaging in battle.

The battlefield can be thought of as $N$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ seas connected to each other by bidirectional rivers, each joining a pair of seas. No sea will be directly connected to itself by a river, but the same pair of seas can be connected by multiple rivers, and it may not be possible to draw the rivers on a map without some of them crossing each other. A river is considered critical if after blocking it, the pair of seas originally joined by it are no longer reachable from each other. Specifically, you can reach a sea $v$ $v$ from another sea $u$ $u$ if there exists a sequence of seas $S_1, S_2, \dots, S_n$ $S_{1}, S_{2}, \dots, S_{n}$ where $n > 1$ $n > 1$ , $S_1 = u$ $S_{1} = u$ , $S_n = v$ $S_{n} = v$ , and $S_i$ $S_{i}$ is connected to $S_{i+1}$ $S_{i + 1}$ for $1 \le i < n$ $1 \leq i < n$ .

You and your fleet girls are immortal, and so you get called upon to fight every few years, for a total of $T$ $T$ $(1 \le T \le 200\,000)$ $(1 \leq T \leq 200 000)$ times. The passage of time is not kind to the battlefield, and so the rivers that connect the seas change often (the seas themselves remain the same though). Normally, this would make it hard to quickly devise a plan for each battle, but there is still hope. In your experience, you have observed that there are $M$ $M$ $(1 \le M \le 100\,000)$ $(1 \leq M \leq 100 000)$ basic formations. A formation is simply a set of rivers, and each battlefield you fight on can be represented by combining two formations (see the sample input for a better understanding).

For each battlefield, you would like to determine the number of critical rivers.

*Kongou, based off of the Kongō.

Input Specification

The first line of input will have $N$ $N$ , $M$ $M$ , and $T$ $T$ , each separated by a single space.

The second line of input will have $T+1$ $T + 1$ numbers, $A_0, A_1, \dots, A_T$ $A_{0}, A_{1}, \dots, A_{T}$ $(1 \le A_i \le M)$ $(1 \leq A_{i} \leq M)$ . The $i^\text{th}$ $i^{th}$ time you fight will be on the battlefield represented by the combination of formations $A_{i-1}$ $A_{i - 1}$ and $A_i$ $A_{i}$ $(1 \le i \le T)$ $(1 \leq i \leq T)$ .

The next $M$ $M$ lines will contain descriptions of a single formation. Formation $i$ $i$ $(1 \le i \le M)$ $(1 \leq i \leq M)$ on line $i+2$ $i + 2$ will be described with $2K_i + 1$ $2 K_{i} + 1$ $(1 \le K_i \le 200\,000)$ $(1 \leq K_{i} \leq 200 000)$ integers in this order: $K_i\ x_{i, 1}\ y_{i, 1}\ \dots\ x_{i, K_i}\ y_{i, K_i}$ $K_{i} x_{i, 1} y_{i, 1} \dots x_{i, K_{i}} y_{i, K_{i}}$ . For each pair $(x_{i, j}, y_{i, j})$ $(x_{i, j}, y_{i, j})$ $(1 \le j \le K_i, x_{i, j} \ne y_{i, j}, 1 \le x_{i, j}, y_{i, j} \le N)$ $(1 \leq j \leq K_{i}, x_{i, j} \neq y_{i, j}, 1 \leq x_{i, j}, y_{i, j} \leq N)$ , there is a river between lakes $x_{i, j}$ $x_{i, j}$ and $y_{i, j}$ $y_{i, j}$ in formation $i$ $i$ .

It is guaranteed that the sum of all $K_i$ $K_{i}$ will not exceed $200\,000$ $200 000$ .

Output Specification

The output should consist of $T$ $T$ lines. Line $i$ $i$ should have the number of critical rivers on the battlefield you fight on for the $i^\text{th}$ $i^{th}$ time $(1 \le i \le T)$ $(1 \leq i \leq T)$ .

Scoring

For test cases worth at least 30% of the points, the additional constraints $N$ $N$ , $M$ $M$ , $K_i$ $K_{i}$ , $T \le 2\,000$ $T \leq 2 000$ will hold.

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

7 3 3
1 2 3 1
4 1 2 1 3 5 7 6 7
4 2 3 3 4 4 5 5 6
3 1 4 4 7 2 6

Sample Output 2

Copy

2
2
2

Explanation for Sample Output 2

Originally, there are 7 seas numbered from 1 to 7.

$\text{[math]}$

The first formation looks like this:

$\text{[math]}$

The second formation looks like this:

$\text{[math]}$

The third formation looks like this:

$\text{[math]}$

In the first battle, the battlefield is made up of the first and second formations and looks like this:

$\text{[math]}$

The two critical rivers (in red) are 3 ↔ 4 and 4 ↔ 5.

In the second battle, the battlefield is made up of the second and third formations and looks like this:

$\text{[math]}$

The two critical rivers (in red) are 1 ↔ 4 and 4 ↔ 7.

In the third and final battle, the battlefield is made up of the third and first formations and looks like this:

$\text{[math]}$

The two critical rivers (in red) are 1 ↔ 3 and 5 ↔ 7.

Comments

0

account_disabled commented on March 20, 2018, 1:24 p.m.

What is the target time complexity?

10

koosaga commented on March 21, 2018, 8:34 a.m. ← edited →

nsqrtpolylog(n), with adequate constant factor.

Constant factor will be important in this problem imo. Better avoid slow-in-practice data structures (like link cut tree, which gives TLE for nsqrt queries in my case)

0

heaven commented on Nov. 11, 2015, 3:20 a.m.

good job admirals