TSOC '15 Contest 2 #4 - Dungeon Crawling - Olympiads Online Judge

TSOC '15 Contest 2 #4 - Dungeon Crawling

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 0.6s

Java 8 1.0s

PyPy 2 1.0s

PyPy 3 1.0s

Memory limit: 391M

Java 8 293M

PyPy 2 293M

PyPy 3 293M

Authors:

omaewamoushindeiru, bobhob314, kobortor

Problem type

The team refuses to risk it in the caves any further, so they decide to hire others to traverse the caves instead. They purchase numerous seasoned ex-convicts from ram.tin.gz and kayv.bon.g.

Using his psychic powers, Mehdi charts out a map of the caves, which are comprised of $N$ ~N~ $(1 \le N \le 20\,000)$ ~(1 \le N \le 20\,000)~ rooms. Cave rooms are numbered from $0$ ~0~ to $N-1$ ~N-1~, inclusive. Rooms are connected by $M$ ~M~ $(1 \le M \le 300\,000)$ ~(1 \le M \le 300\,000)~ one-way paths. $E$ ~E~ of these rooms are entrances $(1 \le E \le 10)$ ~(1 \le E \le 10)~, $D$ ~D~ are destinations $(0 \le D \le 10)$ ~(0 \le D \le 10)~ and some are neither. Destinations do not lead to other rooms but are reachable from other rooms, while entrances have no room which leads to them but have outward paths to other rooms. Mr. Benum is known to be held prisoner in one of the destinations, and the team members can each start from any entrance. There are no cyclic paths. Max has the ex-convicts split up, such that each ex-convict traverses a unique path from an entrance to a destination.

As the organizer of this foray into danger, Max would like to know the following:

How many ex-convicts are needed to take all unique paths?
What is the minimum number of cave rooms that we have to travel through to reach each of the destination rooms (individually) where Mr. Benum may be held?

Input Specification

The first line will contain the integers $N$ ~N~ $M$ ~M~, separated by single spaces. Each of the next $M$ ~M~ lines contain two space-separated integers $a$ ~a~ $b$ ~b~, indicating a unidirectional (one-way) path from $a$ ~a~ to $b$ ~b~.

Output Specification

First line: The total number of team members required to take every possible path through the cave (if one team member can only follow one path), modulo $10^9+7$ ~10^9+7~.

Second line: $D$ ~D~ space-separated integers, with the $i^\text{th}$ ~i^\text{th}~ integer representing the minimum number of different cave rooms that one must pass into to reach the $i^\text{th}$ ~i^\text{th}~ destination room.

Sample Input

Sample Output

3
3 5

Comments

0

const commented on July 5, 2019, 3:04 p.m.

Where do we get E and D? It's not in the input specification.

3

lookcook commented on July 5, 2019, 8:06 p.m.

Destinations do not lead to other rooms but are reachable from other rooms, while entrances have no room which leads to them but have outward paths to other rooms.

-1

P234rex commented on April 30, 2017, 10:37 p.m.

Last test case seems to have 11 destinations.