Problem:


  

  
    MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} });
  
  

  

  
C: ツイート数

  
問題

  
AORイカちゃんが利用するSNSであるイカったーでは、投稿のことをツイートと呼ぶ。

  
そして、イカったーでは、ツイートへの返信が多くなると視認性が悪くなることが懸念されるため、あるツイートが次の規則のいずれかを満たすときに画面にそのツイートを表示する仕様になっている。

  

    
規則１. どのツイートへも返信していない

    
規則２. どのツイートからも返信されていない

    
規則３. 規則２が適用されたツイートから返信先を順に辿ったとき、 $K$ 回未満で辿り着ける

  

  
なお、同じツイートは重複して表示されることはない。

  
いま、 $N$ 個のツイートがあり、 $A_i$ が $0$ のとき $i$ 番目のツイートは返信でないツイートで、 $A_i$ が $0$ でないとき $i$ 番目のツイートは $A_i$ 番目のツイートへの返信のツイートである。

  
画面に表示されるツイート数を答えよ。

  
制約

  

    
$1 \le N \le 10^5$

    
$1 \le K \le 10^5$

    
$0 \le A_i \lt i (i = 1, 2, \dots, N)$

    
ツイートは時系列順に与えられる。

    
入力は全て整数で与えられる。

  

  
入力形式

  
入力は以下の形式で与えられる。

  
$N \ K$
$A_1$
$A_2$
$\vdots$
$A_N$

  
出力

  
画面に表示されるツイート数を出力せよ。また、末尾に改行も出力せよ。

  
サンプル

  
サンプル入力 1

  
6 3
0
0
2
3
4
5

  
サンプル出力 1

  
5

  
この時、表示されるツイートは、図の青いツイートである。 よって、この例の解は $5$ である。

  

  
サンプル入力 2

  
12 2
0
1
0
3
4
3
6
7
0
9
10
11

  
サンプル出力 2

  
10

  
サンプル入力 3

  
5 10
0
0
0
0
0

  
サンプル出力 3

  
5

  

Sample input:
6 3
0
0
2
3
4
5


Sample output:
5

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
end = set()
add = end.add
result = 0
for i in range(N-1, -1, -1):
    if a[i] == -1:
        result += 1
    elif i in end:
        continue
    else:
        v = i
        l = 0
        while v != -1 and v not in end:
            l += 1
            add(v)
            v = a[v]
        result += min(l-(v==-1), K)


print(result)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    if a[i] > -1 and a[a[i]] > -1:
        hoge_add(a[i])
nodes -= {-1}

startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        result += 1
        v = a[v]
        while a[v] != -1 and v not in nodes and l > 0:
            result += 1
            l -= 1
            v = a[v]
        if v in nodes and l > 0:
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        result += 1
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            result += 1
            l -= 1
            v = a[v]
        if v > -1 and a[v] > -1 and v in nodes:
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += 1
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            result += 1
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += 1
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += (v not in visited)
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
end = set()
end2 = set()
add = end.add
add2 = end2.add
result = 0
for i in range(N-1, -1, -1):
    if a[i] == -1:
        result += 1
    elif i in end:
        continue
    else:
        v = i
        l = 0
        n = 0
        while a[v] != -1:
            if v not in end2 and l < K:
                n += 1
                add2(v)
            l += 1
            add(v)
            v = a[v]
        result += n


print(result)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
end = set()
end2 = set()
add = end.add
add2 = end2.add
result = a.count(-1)

leaves = {i for i in range(N) if a[i] > -1} - set(a)
for i in leaves:
    v = i
    l = 0
    n = 0
    while a[v] != -1:
        if v not in end2 and l < K:
            n += 1
            add2(v)
        l += 1
        v = a[v]
    result += n

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
result = a.count(-1)

leaves = {i for i in range(N) if a[i] > -1} - set(a)
dq = deque()
append = dq.append
for i in leaves:
    v = i
    l = 0
    while a[v] != -1 and l < K:
        append(v)
        l += 1
        v = a[v]

print(result+len(set(dq)))

Submission status: Time Limit Exceeded

Solution code:
#????????????ACPC2017Day1_C Displayed tweets
#URL???http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=C
#???????????????
#???????????????

s = input().split()
N = int(s[0])
K = int(s[1])
A = [0]
B = [0]
C = [K]
cnt = 0

for h in range(N):
    x = input()
    x = int(x)
    A.append(x)
    B.append(0)
    C.append(K)
    
for i in range(N):
    if A[i+1] != 0:
        B[A[i+1]] += 1

if K > 1:
    for j in range(N):
        if B[j+1] == 0:
            k = 0
            m = j+1
            for k in range(K-1):
                C[A[m]] = k+1
                m = A[m]

for l in range(N):
    if A[l+1]*B[l+1] == 0:
        cnt += 1
    elif C[l+1] < K:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# AOJ 2833: Displayed tweets
# Python3 2018.7.12 bal4u

INF = 0x7ffffff

N, K = map(int, input().split())
k, f = [INF]*(N+1), [0]*(N+1)
a = [0]+[int(input()) for i in range(N)]
ans = 0
for i in range(N, 0, -1):
	re = a[i]
	if re:
		if f[i] == 0: v = 0; ans += 1
		else:
			v = k[i]
			if v < K: ans += 1
		v += 1
		if v < K and k[re] > v: k[re] = v
		f[re] = 1;
	else: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += (v not in visited)
        add(v)
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)