Submission #3767827


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)
      

  

    
    
      
    
    
      
  
  
  
    
    
  
  
  
  
  
  

Submission Info

Submission Time
Task F - Coins on the tree
User Chanyuh
Language PyPy3 (2.4.0)
Score 0
Code Size 1130 Byte
Status WA
Exec Time 277 ms
Memory 46300 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
WA × 2
WA × 42
Set Name Test Cases
Sample s1.txt, s2.txt
All 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 WA 198 ms 41584 KB
02.txt WA 200 ms 42204 KB
03.txt WA 211 ms 42732 KB
04.txt WA 212 ms 42844 KB
05.txt WA 202 ms 42460 KB
06.txt WA 272 ms 46300 KB
07.txt WA 258 ms 43868 KB
08.txt WA 267 ms 45276 KB
09.txt WA 260 ms 44508 KB
10.txt WA 270 ms 45404 KB
11.txt WA 268 ms 45404 KB
12.txt WA 262 ms 45276 KB
13.txt WA 262 ms 45276 KB
14.txt WA 258 ms 45020 KB
15.txt WA 269 ms 45532 KB
16.txt WA 248 ms 44380 KB
17.txt WA 261 ms 45532 KB
18.txt WA 258 ms 45148 KB
19.txt WA 252 ms 44636 KB
20.txt WA 257 ms 44124 KB
21.txt WA 264 ms 44764 KB
22.txt WA 246 ms 43996 KB
23.txt WA 277 ms 44764 KB
24.txt WA 270 ms 46044 KB
25.txt WA 276 ms 45660 KB
26.txt WA 267 ms 44892 KB
27.txt WA 254 ms 43996 KB
28.txt WA 256 ms 45020 KB
29.txt WA 274 ms 44508 KB
30.txt WA 256 ms 44764 KB
31.txt WA 234 ms 44380 KB
32.txt WA 208 ms 42860 KB
33.txt WA 224 ms 42992 KB
34.txt WA 180 ms 39536 KB
35.txt WA 260 ms 43868 KB
36.txt WA 269 ms 45660 KB
37.txt WA 225 ms 44508 KB
38.txt WA 230 ms 44124 KB
39.txt WA 273 ms 45916 KB
40.txt WA 256 ms 45404 KB
s1.txt WA 165 ms 38256 KB
s2.txt WA 166 ms 38256 KB