oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

cousin Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

cousin.html

Problem Description

Gug the Amoeba has a long family heritage. There are a total of N amoeba in his family, with the eldest of them all being Amoeba 0. For all other amoebas, they have a single parent. Namely, amoeba i has parent Pi. It is guaranteed that there will be no loops in the family tree, meaning that no direct or indirect parent of an amoeba will be itself.

We call a pair of distinct amoebas k-cousins if they share a common k-th parent. Gug wants to know, for some amoebas in his family, how many k-cousins they have.

Implementation Details

This is a function call problem. You are to implement 2 functions:

void init(int N, int P[])

This function will be called before any of the other functions in your code. N is the number of amoebas in Gug's family tree and P is the parent array of his family tree. Since Amoeba 0 has no parent, P0 = -1.

int count_cousins(int X, int K)

This function should return the number of K-cousins that Amoeba X has. It is guaranteed that Amoeba X has at least K parents.

Limits

Subtask 1 (27%): 1 ≤ N ≤ 1000, Number of calls to count_cousins ≤ 3000.

Subtask 2 (20%): 1 ≤ N ≤ 200000, K ≤ 5, Number of calls to count_cousins ≤ 300000.

Subtask 3 (22%): 1 ≤ N ≤ 200000, K is a constant throughout all calls to count_cousins, Number of calls to count_cousins ≤ 300000.

Subtask 4 (31%): 1 ≤ N ≤ 200000, Number of calls to count_cousins ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Interaction

init(7, [-1, 0, 1, 1, 0, 4, 4]) will be called.
count_cousins(2, 1) is called. It should return 1.
count_cousins(6, 1) is called. It should return 1.
count_cousins(3, 2) is called. It should return 3.

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
127211s256MBMinimum
220211s256MBMinimum
322201s256MBMinimum
431811s256MBMinimum
5011s256MBMinimum

Attachments

Attachment Filesize Last Updated
sample.out6B16 Dec 2017, 11:10:31
cousin.h61B16 Dec 2017, 11:10:53
grader.cpp301B16 Dec 2017, 11:11:56
ans.cpp102B16 Dec 2017, 11:11:22
sample.in31B16 Dec 2017, 11:10:27

Judge Compile Command

g++-8 grader.cpp ans.cpp -o cousin -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.