Submission #13244032


Source Code Expand

Copy
n,m,k=map(int,input().split())
p=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for i in range(n):
  if p[i]:edge[p[i]-1].append(i)
  else:r=i
def bfs(v,t):
  stack=[r]
  d=[-1]*n
  d[r]=1
  x=[1]
  if t==r:return[[],1]
  ans=-1
  for i in stack:
    for j in edge[i]:
      if j==t:ans=d[i]+1;continue
      if j in v:continue
      stack.append(j)
      d[j]=d[i]+1
      x.append(d[j])
  return [sorted(x),ans]
v=set()
ans=[]
for i in range(m):
  w=m-i-1
  for j in range(n+1):
    if j==n:exit(print(-1))
    if j in v:continue
    x,a=bfs(v,j)
    if a==-1 or len(x)<w:continue
    if sum(x[:w])<=k-a<=sum(x[::-1][:w]):
      k-=a
      ans.append(j+1)
      v.add(j)
      break
print(*ans)

Submission Info

Submission Time
Task F - Coins on the tree
User tyawanmusi
Language Python3 (3.4.3)
Score 400
Code Size 742 Byte
Status
Exec Time 1172 ms
Memory 3188 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt 21 ms 3064 KB
02.txt 19 ms 3188 KB
03.txt 18 ms 3064 KB
04.txt 21 ms 3064 KB
05.txt 19 ms 3064 KB
06.txt 127 ms 3064 KB
07.txt 61 ms 3064 KB
08.txt 50 ms 3064 KB
09.txt 128 ms 3064 KB
10.txt 833 ms 3188 KB
11.txt 253 ms 3188 KB
12.txt 622 ms 3064 KB
13.txt 968 ms 3064 KB
14.txt 726 ms 3064 KB
15.txt 289 ms 3188 KB
16.txt 873 ms 3064 KB
17.txt 334 ms 3064 KB
18.txt 902 ms 3188 KB
19.txt 514 ms 3188 KB
20.txt 644 ms 3188 KB
21.txt 404 ms 3188 KB
22.txt 829 ms 3188 KB
23.txt 808 ms 3188 KB
24.txt 554 ms 3188 KB
25.txt 762 ms 3188 KB
26.txt 957 ms 3064 KB
27.txt 975 ms 3188 KB
28.txt 844 ms 3188 KB
29.txt 1172 ms 3188 KB
30.txt 806 ms 3188 KB
31.txt 26 ms 3064 KB
32.txt 18 ms 3064 KB
33.txt 20 ms 3064 KB
34.txt 18 ms 3064 KB
35.txt 44 ms 3064 KB
36.txt 53 ms 3064 KB
37.txt 18 ms 3064 KB
38.txt 18 ms 3064 KB
39.txt 19 ms 3064 KB
40.txt 27 ms 3064 KB
s1.txt 17 ms 3064 KB
s2.txt 17 ms 3064 KB