Connection Status:
Competition Arena > OwaskiAndTree

OwaskiAndTree

SRM 719 · 2017-07-25 · by matthew99a

SRM 719 · 2017-07-25 · by matthew99a · Dynamic Programming
Class Name: OwaskiAndTree
Return Type: int
Method Name: maximalScore
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Owaski is another pet dog of Zhangzj. He likes playing on a tree.

The tree has N vertices, labeled from 0 to N - 1. You are given an int[] parent of N - 1 elements. For each i between 0 and N - 2, inclusive, there is an edge between vertex i + 1 and vertex parent[i]. In a single step, Owaski can walk from a vertex to one of its adjacent vertices. You are given an int[] pleasure, element i of which indicates the pleasure Owaski gets when he reaches vertex i. Before entering the tree, his pleasure is 0. Of course, at some moments Owaski's pleasure can be negative, as some vertices can make him unhappy. However, Owaski doesn't like to be unhappy. Thus whenever his pleasure becomes negative, he will make it zero again by playing Overwatch and winning nearly every game. Owaski may enter each vertex arbitrarily many times. However, he doesn't like old things. Thus, if he enters a vertex he visited before, his pleasure remains unchanged. In other words, each vertex only influences Owaski's pleasure when he visits it for the first time.

Owaski enters the tree at vertex 0 (therefore the pleasure of vertex 0 also counts), and can leave the tree whenever he wants. Since all dogs love to be happy, he wants to leave with as much pleasure as possible. Return the maximal pleasure he can get.

Constraints

  • N will be between 1 and 1,000, inclusive.
  • parent will contain exactly N - 1 elements.
  • pleasure will contain exactly N elements.
  • For each i, parent[i] will be between 0 and i, inclusive.
  • Each element of pleasure will be between -1,000,000 and 1,000,000, inclusive.
Examples
0)
{0, 1, 2, 3, 4, 5, 6, 7, 8}
{1, 1, -1, -1, -1, -1, 1, 1, 1, 1}
Returns: 4

The tree forms a chain of 10 vertices and 9 edges. The optimal way is to walk through the chain. The values of pleasure of Owaski after visiting vertex 0 to 9 are 1, 2, 1, 0, 0, 0, 1, 2, 3, 4, respectively. He can leave the tree after that, yielding net pleasure of 4.

1)
{0, 0, 1, 2}
{2, 3, 4, -1, -1}
Returns: 9

This time his path can be 0 → 1 → 0 → 2. Note that although Owaski visits 0 twice, the pleasure of that vertex only counts once.

2)
{0, 0, 1, 1, 2, 2, 5, 5}
{1, 2, -3, -7, 3, 2, 7, -1, 3}
Returns: 17

One of the optimal paths is 0 → 2 → 5 → 8 → 5 → 2 → 6 → 2 → 0 → 1 → 4.

3)
{0, 1, 1, 1, 0, 3, 1, 3, 4, 4, 3, 6, 8, 0, 12, 12, 11, 7, 7}
{-154011, 249645, 387572, 292156, -798388, 560085, -261135, -812756, 191481, -165204, 81513, -448791, 608073, 354614, -455750, 325999, 227225, -696501, 904692, -297238}
Returns: 3672275
4)
{}
{-1}
Returns: 0

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

Coding Area

Language: C++17 · define a public class OwaskiAndTree with a public method int maximalScore(vector<int> parent, vector<int> pleasure) · 195 test cases · 2 s / 256 MB per case

Submitting as anonymous