[PYTHON] Atcoder Begginer Contst 065 - B: Ausgebildet?

Atcoder Begginer Contst 065 -- B: Trained? https://atcoder.jp/contests/abc065 Die folgenden zwei Codes sind bis auf die Anzahl der Variablen alle gleich. Es war Version1 => AC, Version2 => TLE. Es gibt einen Unterschied zwischen bool und int, daher kann ich das Anhängen nicht beschuldigen, aber ich dachte nicht, dass es so viel bewirken würde wie TLE ...

version1.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = [False]*N
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif count[push]:
      break
      
    else:
        count[push] = True
        push = A[push] 
      
print(ans)

version2.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = []
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif A[push] in count:
      break
      
    else:
      count.append(push)
      push = A[push]
        
print(ans)

Oder die 15. Zeile von Version 2

elif A[push] in count:
    break

Kann langsam sein ...? Sie müssen vorsichtig sein, wenn Sie mit der Ikansen-Liste umgehen ... Wenn jemand die Ursache kennt, bitte kommentieren.

Nachtrag

Ich habe die Zählvariable von list in set geändert und es gibt keine TLEs mehr. Immerhin denke ich, dass xx in der Liste langsam war.

Fazit: Verwenden Sie xx im Set anstelle von xx in der Liste.

version3.py

N = int(input())
A = []
for i in range(N):
  A.append(int(input())-1)
    
ans = -1
push = 0
count = set()
 
for i in range(N+1):
 
    if A[push] == 1:
        ans = i+1
        break
        
    elif A[push] in count:
      break
      
    else:
      count.add(push)
      push = A[push]
        
print(ans)