Connection Status:
Competition Arena > TwoEntrances

TwoEntrances

SRM 654 · 2015-01-29 · by sigma425

SRM 654 · 2015-01-29 · by sigma425 · Recursion, Simple Math
Class Name: TwoEntrances
Return Type: int
Method Name: count
Arg Types: (vector<int>, vector<int>, int, int)
Problem Statement

Problem Statement

There are N rooms in Maki's new house. The rooms are numbered from 0 to N-1. Some pairs of rooms are connected by bidirectional passages. The passages have the topology of a tree. That is, there are exactly N-1 of them and it is possible to go from any room to any other room by following some sequence of passages.

You are given two int[]s a and b that describe the passages. For each valid i, there is a passage that connects the rooms a[i] and b[i]. You are also given two ints: s1 and s2 The house has exactly two entrances from the outside. One leads to the room s1, the other leads to the room s2.

Niko is helping Maki move into the new house. Maki has exactly N pieces of furniture. The pieces are numbered from 0 to N-1. Niko will carry them into the house in this order. Each piece of furniture must be placed into a different room. Maki does not care which piece goes where, each of the N! permutations is allowed.

However, not all of those N! permutations are actually possible. This is because the furniture is large. As soon as a room contains a piece of furniture, it is impossible to move other pieces through this room. Thus, Niko must place the furniture carefully. Formally, she can place a new piece of furniture into the room x if and only if there is a path from one of the entrances to x that consists only of empty rooms. (For any room x, there is exactly one path from s1 to x and exactly one path from s2 to x. At least one of these two paths must be completely empty.)

Niko is smart and she will always place the furniture in such a way that she never gets stuck. Thus, at the end each of Maki's rooms will contain exactly one piece of furniture.

Let X be the number of ways how the furniture can be arranged in Maki's house at the end. As X can be large, calculate and return the value (X modulo 1,000,000,007).

Constraints

  • N will be between 2 and 3000, inclusive.
  • a and b will contain exactly N-1 elements each.
  • Each element of a and b will be between 0 and N-1, inclusive.
  • The graph described by a and b will be a tree.
  • s1 and s2 will be between 0 and N-1, inclusive.
  • s1 and s2 will be different.
Examples
0)
{0, 1, 2}
{1, 2, 3}
0
1
Returns: 4

Niko must fill the rooms in one of the following four orders: {3,2,1,0}, {3,2,0,1}, {3,0,2,1}, or {0,3,2,1}. (Note that, for example, she cannot place a piece of furniture into room 2 before he places another piece into room 3.)

1)
{0, 1, 2}
{1, 2, 3}
0
2
Returns: 9
2)
{0, 1, 1, 3, 3, 3, 6, 7, 6}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
1
9
Returns: 16000
3)
{0, 0, 1, 2, 3, 1, 2, 0, 6, 5, 10, 10}
{1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10, 11, 12}
3
6
Returns: 310464
4)
{0}
{1}
1
0
Returns: 2

Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoEntrances with a public method int count(vector<int> a, vector<int> b, int s1, int s2) · 128 test cases · 2 s / 256 MB per case

Submitting as anonymous