TwoDogsOnATree
SRM 719 · 2017-07-25 · by matthew99a
Problem Statement
LYC and owaski are pet dogs of Zhangzj. They like playing on a tree.
The tree has N vertices, indexed from 0 to (N - 1). On each edge of the tree, there is a number between 0 and 1,023, inclusive. LYC will choose a path on the tree, calculate the bitwise xor of the numbers on the edges of the path. (The bitwise xor of zero numbers is 0. This applies if the path has no edges.) Then, LYC will erase all edges of the path. This will divide the tree into several connected components, each of which will be a tree again.
Once LYC is done, Owaski will choose one of those components. Then, he will choose a path in that component and calculate the bitwise xor of the numbers on its edges.
Finally, the two dogs will share the values they computed with each other, and together they will compute one final number F: the bitwise xor of their two numbers. Their goal is to work together to maximize the value of F. You are given
Compute and return the largest possible value of the final number F.
Constraints
- N will be between 1 and 1,000, inclusive.
- Both parent and w will contain exactly (N - 1) elements.
- For each valid i, parent[i] will be between 0 and i, inclusive.
- For each valid i, w[i] will be between 0 and 1,023, inclusive.
{0, 0, 0, 0}
{1, 2, 4, 8}
Returns: 15
The tree contains 5 vertices and 4 edges. LYC can choose the path 1 &rarr 0 &rarr 2, and Owaski can choose the path 3 &rarr 0 &rarr 4. LYC's number will be 1 xor 2 = 3. Owaski's number will be 4 xor 8 = 12. The answer will be 3 xor 12 = 15.
{0, 1, 2, 3, 4, 5, 6, 7, 8}
{3, 2, 6, 5, 8, 1, 3, 4, 3}
Returns: 15
The tree forms a chain of 10 vertices and 9 edges. LYC can choose the whole chain, and Owaski can choose a path containing a single vertex. The number LYC gets will be 15, and because Owaski's path contains no edges, the number will be 0. Therefore the answer will be 15 xor 0 = 15.
{0, 0, 2, 2, 4, 4, 5, 6}
{13, 16, 12, 11, 3, 1, 4, 2}
Returns: 31
LYC can choose the path 4 &rarr 6 &rarr 8, and Owaski can choose the path 0 &rarr 2 &rarr 3.
{0, 0, 2, 0, 1, 2, 2, 4, 6, 1, 5}
{628, 589, 815, 864, 459, 507, 733, 239, 904, 592, 818}
Returns: 1017
{}
{}
Returns: 0
Submissions are judged against all 240 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoDogsOnATree with a public method int maximalXorSum(vector<int> parent, vector<int> w) · 240 test cases · 2 s / 256 MB per case