Connection Status:
Competition Arena > TreePuzzle

TreePuzzle

TCO14 Round 2A · 2014-03-26 · by rng_58

TCO14 Round 2A · 2014-03-26 · by rng_58 · Graph Theory
Class Name: TreePuzzle
Return Type: int[]
Method Name: reachable
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Cat Snuke has a tree with N nodes. The nodes are numbered 0 through N-1. You are given a int[] parent that represents the structure of the tree. The value parent[0] should be ignored. For each i > 0, there is an edge that connects the nodes i and parent[i].

Initially, Snuke placed a red token onto node 0, and black tokens onto some of the other nodes (possibly none or all of them). You are given this information as a int[] token with N elements. For each i, token[i] will be either 0 or 1. Here, 0 means that node i is empty, and 1 means that it contains a token. It is guaranteed that token[0]=1.

Snuke now plays a game with the tokens. Whenever there is a node with a token adjacent to an empty node, Snuke may slide the token along the edge from its current node to the adjacent empty one. The goal of the game is to move the red token into a specific node.

Return a int[] with N elements. For each i, element i of the return value should be 1 if it is possible to reach node i with the red token, and 0 otherwise.

Constraints

  • N will be between 2 and 300, inclusive.
  • parent will contain exactly N elements.
  • parent[0] will be -1.
  • For each i > 0, parent[i] will be between 0 and i-1, inclusive.
  • token will contain exactly N elements.
  • token[0] will be 1.
  • For each i > 0, token[i] will be either 0 or 1.
Examples
0)
{-1, 0, 0, 0, 1}
{1, 1, 0, 0, 1}
Returns: {1, 1, 1, 1, 0 }

In the figure below, each row shows a sequence of moves that starts from the initial configuration and ends with the red token reaching one of the nodes 0, 1, 2, and 3. There is no valid sequence of moves such that the red token reaches the node 4.

1)
{-1, 0, 1, 0, 3, 2, 5, 6, 7, 8}
{1, 1, 1, 1, 1, 1, 0, 0, 1, 0}
Returns: {1, 1, 1, 0, 0, 1, 0, 0, 0, 0 }
2)
{-1, 0, 0, 2, 1, 1, 5, 0, 0, 2}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
3)
{-1, 0, 1, 2, 3, 4, 5, 0, 7, 6, 8, 9, 11, 0, 11, 2, 15, 13, 15, 10}
{1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: {1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 }
4)
{-1, 0, 1, 2, 3, 4, 0, 5, 7, 8, 6, 10, 11, 9, 13, 14, 12, 16, 16, 18,
15, 10, 17, 2, 23, 22, 21, 20, 27, 24, 19, 30, 28, 29, 17, 21, 34, 35, 31, 30,
36, 32, 31, 39, 26, 40, 3, 38, 45, 25, 49, 46, 41, 44, 51, 47, 18, 54, 48, 36,
43, 57, 52, 56, 60, 59, 53, 61, 64, 68, 37, 55, 71, 32, 26, 73, 28, 50, 75, 72,
70, 67, 74, 66, 79, 76, 78, 63, 69, 41, 83, 86, 80, 18, 82, 87, 58, 62, 42, 20}
{1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0 }

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

Coding Area

Language: C++17 · define a public class TreePuzzle with a public method vector<int> reachable(vector<int> parent, vector<int> token) · 216 test cases · 2 s / 256 MB per case

Submitting as anonymous