Gym — Samara University ACM ICPC 2016-2017 Quarterfinal Qualification Contest

Gym — Samara University ACM ICPC 2016-2017 Quarterfinal Qualification Contest

By dalex, 6 years ago, translation,

• 6 years ago, # ^ | ← Rev. 2 →   0 Is it guaranteed that the graph formed by dependencies is a connected one, or at least that A and B are in the same connection component? If so, could you please tell me where it is mentioned/implied? Thanks)

  • 6 years ago, # ^ | you can find this description in the Input section. It's guaranteed that it's possible to acquire all (n+1) talents given the infinite number of talent points.

    • 6 years ago, # ^ | Well, for instance, if we take a graph with no edges at all, wouldn't it suit this condition? We will be able to acquire all the skills, and we would only need 2 points to directly purchase A and B.

      • 6 years ago, # ^ | ← Rev. 2 →   0 You might have misunderstood the problem but you looks smart because you tried to understand the statement carefully. Maybe, you've thought you can immediately get some skill which doesn't have any skills need to master in advance. But here is a description which can correct your understanding. A talent can be acquired only if a character has at least one of the talents it depends on. If a skill has no skill it depend on, you can't satisfy the condition "at least one of talents..." and you can't get the skill. Such a case violates the constraints.

        • 6 years ago, # ^ | ← Rev. 2 →   0 Understood it now, thanks a lot! :) I thought exactly like you wrote before) Didn't consider this sentence restrictive while reading the problem description.

• 6 years ago, # ^ | I tried doing a downward DFS from 0 storing at every node the minimum distance to A below it in the DFS tree, minimum distance to B and minimum distance to both A and B (means the no. of skill points needed to get both A and B if we have the current node.) For a given node n, a_val[n] = min(a_val[child] + 1) for all children of n. b_val[n] = min(b_val[child] + 1) for all children of n. ab_val[n] = min(ab_val[child] + 1) for all children of n. if(a_val[n] + b_val[n] < ab_val[n]) ab_val[n] = a_val[n] + b_val[n]; The answer is in ab_val[0] The code is given below Solution Link Could anyone please tell me why it's failing? (Test Case 18) Thank you

• 4 years ago, # ^ | ← Rev. 2 →   0 code please of problem L ??