Submission #3767727

---

Source Code Expand

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**9)
N,M,K=map(int,input().split())
p=[int(i) for i in input().split()]
inf=float("inf")
Graph=defaultdict(set)
for i in range(N):
  if p[i]!=0:
    Graph[i].add(p[i]-1)
    Graph[p[i]-1].add(i)
  else:
    root=i
dfs=deque([root])
par=[[-1]*N for i in range(20)]
dist=[-1]*N 
dist[root]=1
while dfs:
  p=dfs.popleft()
  for i in Graph[p]:
    if dist[i]<0:
      dist[i]=dist[p]+1
      par[0][i]=p
      dfs.append(i)
      
for i in range(1,18):
  for j in range(N):
    if par[i-1][j]>0:
      par[i][j]=par[i-1][par[i-1][j]]
    
def lca(x,y):
  if dist[x]>dist[y]:
    x,y=y,x
  for i in range(18):
    if (dist[y]-dist[x])& 1<<i:
      y=par[i][y]
  if x==y:
      return y
  for i in range(17,-1,-1):
    if par[i][x]!=par[i][y]:
      x=par[i][x]
      y=par[i][y]
  return par[0][y]

C=[[] for i in range(N)]
for i in range(N):
  for j in range(N):
    if lca(i,j)==i:
      C[i].append(j)
      
def f(l,k,m):
  if m==M:
    for i in range(N):
      if dist[i]==k and l[i]:
        return [i+1]
    return -1
  else:
    for i in range(N):
      if dist[i]<=k and l[i]:
        l_next=l[::]
        for c in C[i]:
          l_next[c]=False
        if f(l_next,k-dist[i],m+1)!=-1:
          res=f(l_next,k-dist[i],m+1)
          res.append(i+1)
          return res
  return -1
a=f([True]*N,K,1)
if a==-1:
  print(-1)
else:
  ans=list(reversed(a))
  print("a".join(list(map(str,ans))))

      
      
  

    
    
      
    
    
      
  
  
  
    
    
  
  
  
  
  
  

Submission Info

Judge Result