PublicTransitHard
SRM 659 · 2015-05-01 · by zxqfl
SRM 659 · 2015-05-01 · by zxqfl · Graph Theory, Sorting
Problem Statement
Problem Statement
Note that this problem has a time limit of 3 seconds.
The city of Treeonto is a tree of N vertices numbered from 0 to N-1. For each valid i, an edge connects vertex i+1 and vertex edges[i]. Travelling along an edge in the graph takes one minute.
The citizens of Treeonto are upset that it takes too long to get around, so they have decided to build a teleporter. The teleporter will consist of two identical booths, each located in some vertex. If a citizen enters either booth, he or she may choose to teleport to the other booth instantly. It is allowed to build both booths in the same vertex.
We define the distance between two vertices as the smallest number of minutes needed to get from one vertex to the other. Let D be the maximum distance between any two vertices. Return the number of ways to place the teleporter such that D does not exceed X.
The city of Treeonto is a tree of N vertices numbered from 0 to N-1. For each valid i, an edge connects vertex i+1 and vertex edges[i]. Travelling along an edge in the graph takes one minute.
The citizens of Treeonto are upset that it takes too long to get around, so they have decided to build a teleporter. The teleporter will consist of two identical booths, each located in some vertex. If a citizen enters either booth, he or she may choose to teleport to the other booth instantly. It is allowed to build both booths in the same vertex.
We define the distance between two vertices as the smallest number of minutes needed to get from one vertex to the other. Let D be the maximum distance between any two vertices. Return the number of ways to place the teleporter such that D does not exceed X.
Constraints
- N will be between 1 and 2000, inclusive.
- edges will contain N-1 elements.
- For each valid i, edges[i] will be between 0 and i, inclusive.
- X will be between 0 and N, inclusive.
Examples
0)
4
{0, 1, 2}
1
Returns: 1
1)
3
{0, 0}
2
Returns: 6
Any teleporter placement is valid.
2)
6
{0, 0, 0, 1, 1}
2
Returns: 1
3)
7
{0, 1, 0, 1, 2, 4}
3
Returns: 0
4)
16
{0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6}
7
Returns: 31
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PublicTransitHard with a public method int countValidTeleporters(int N, vector<int> edges, int X) · 112 test cases · 2 s / 256 MB per case