Submission #4659991

---

Source Code Expand

import sys
sys.setrecursionlimit(10**6)
N,M,K=map(int,input().split())
Graph=[int(i)-1 for i in input().split()]
Tree=[[] for i in range(N)]
for i,p in enumerate(Graph):
  if p!=-1:
    Tree[p].append(i)
  else:
    root=i
depth=[0]*N
count=[0]*N
size=[0]*N
def dfs_depth(x,d):
  depth[x]=d
  for y in Tree[x]:
    dfs_depth(y,d+1)
    
def dfs(x):
  S,C=1,depth[x]+1
  for y in Tree[x]:
    s,c=dfs(y)
    S+=s
    C+=c
  size[x],count[x]=S,C
  return (S,C)

dfs_depth(root,0)
dfs(root)

def check(x,k,m):
  if size[x]==0:
    return False
  if depth[x]+1>k or (depth[x]+1)+(count[root]-count[x])<k:
    return False
  if 1+(size[root]-size[x])<m:
    return False
  return True
ans=[]
k_,m_,flag=0,0,False
for i in range(M):
  for p in range(N):
    if check(p,K-k_,M-m_):
      ans.append(str(p+1))
      flag=True
      break
  if not flag:
    print(-1)
    exit()
  else:
    k_+=depth[p]+1
    m_+=1
    if p!=root:
      Tree[Graph[p]].remove(p)
      count,size=[0]*N,[0]*N
      dfs(root)
  flag=False
print(" ".join(ans))

Submission Info

Judge Result