Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import product, combinations,permutations
from copy import deepcopy
import sys
sys.setrecursionlimit(4100000)



if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split())) 

    prev = 1
    memo = []
    loop_start_index = 0
    while True:
        nxt = A[prev]
        if nxt not in memo:
            memo.append(nxt)
        else:
            end = nxt
            break
        prev = nxt
        loop_start_index += 1 
    start = 0
    for i, m in enumerate(memo):
        if m==end:
            start = i 
    d = loop_start_index-start
    if K<=start:
        print(memo[K])
    else:
        K -= 1
        print(memo[K%d])

Submission status: Wrong Answer

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

# n:number of town, k: visit times
_,k = LI()
# next place array
a = LI()
# 街の番号を0始まりに変更
a = list(map(lambda x:x-1,a))

# 再帰関数
def rec(visited,next):
    if next in visited:
        return visited,next
    else:
        visited.add(next)
        return rec(visited,a.pop())

visited = set([1])
# 訪れた街、初めて2回目に訪れた街を取得
visited,firstReturn = rec(visited,a.pop())
# print(visited,firstReturn)
visitedList = list(visited)
# loopの開始位置
start = visitedList.index(firstReturn)
# print('start:',start)

if k<=len(visitedList):
    print(visitedList[k]+1)
else:
    visitedListLoop = visitedList[start:]
    # print('visitedListLoop:',visitedListLoop)
    end = (k-(start+1))%len(visitedListLoop)
    # print('end:',end)
    print(visitedListLoop[end]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
a = [0] + list(map(int,input().split()))

now = 1
arrive = [0] * (n+1)
arrive[1] = now

for i in range(2,n+1):
    now = a[now]
    arrive[i] = now

loop = -1
q = [0] * (n+1)

for i in arrive[::-1]:
    q[i] += 1
    loop += 1
    if any(x > 1 for x in q): break

if k < n:
    print(arrive[k+1])
else:
    k %= loop
    print(arrive[k+1])

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
data = list(map(int, input().split()))
town = [0] * N
temp = []
once = []



p = 1 #pointer
for i in range(N):
  temp.append(p-1)
  if town[p-1] == 1:
    break
  else:
    town[p-1] = 1
    p = data[p-1]
    #print(town)
    #print("pointer = {}".format(p))

#print(temp)

while True:
  if temp[0] == temp[-1]:
    break
  else:
    once.append(temp[0])
    temp.pop(0)


temp.pop(-1)
#print(once)
#print(temp)

K = K - len(once)
K = K % len(temp)
print(temp[K]+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
  N,M=map(int,input().split())
  L=list(map(int,input().split()))
  i=1
  R=list()
  for j in range(N+1):
    if L[i-1] in R:
      c=R.index(L[i-1])
      t=len(R)-c
      m=R[c:]#ループ
      break
    R.append(L[i-1])
    i=L[i-1]
  l=(M-c-1)%t
  print(m[l])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=1
L=[1]
for i in range(N+2):
  m=A[m-1]
  if m not in L:
    L.append(m)
  else:
    L.append(m)
    break
c=L.index(m)
le=len(L)
#le-cでループ　c,le,2*le-c....
rupe=le-c-1
a=K%rupe
if a<c:
  a+=rupe
print(L[a])

Submission status: Wrong Answer

Solution code:

N, K = map(int, input().split())
X = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(40)]
dp[0] = [0] + X
for k in range(1, 40):
    for i in range(N + 1):
        dp[k][i] = dp[k - 1][dp[k - 1][i]]

ans = 1
for i in range(40):
    if K >> i & 1:
        ans = dp[i][ans]

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))

journey = [1]

for i in range(n):
    journey.append(a[journey[i]])

cycle_end = n
cycle_start = n - 1

while journey[cycle_start] != journey[cycle_end]:
    cycle_start -= 1

cycle_range = cycle_end - cycle_start

cycle_cnt = (k - n) // cycle_range
extra = (k - n) - (cycle_range * cycle_cnt)

for i in range(extra):
    journey.append(a[journey[i + n]])    

print(journey[-1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]

l=[0 for i in range(n)]
cnt=0

dist=[]
now=0
while(True):
  
  if l[now]+1==3:
    break
  dist.append(now)

  l[now]+=1
  now=a[now]-1


k=k-l.count(1)
g=l.count(2)
# print(dist)
# print(l)


dist=dist[l.count(1):]

print(dist[k%g]+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]

l=[0 for i in range(n)]
cnt=0

dist=[]
now=0
while(True):
  
  if l[now]+1==3:
    break
  dist.append(now)

  l[now]+=1
  now=a[now]-1


k=k-l.count(1)
g=l.count(2)
# print(dist)
# print(l)
if k<=n:
  now=0
  for i in range(n):
    now=a[now]-1
  print(now+1)
    
else:
  print(dist[k%g+l.count(1)]+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]

l=[0 for i in range(n)]
cnt=0

dist=[]
now=0
while(True):
  
  if l[now]+1==3:
    break
  dist.append(now)

  l[now]+=1
  now=a[now]-1


# k=k-l.count(1)
g=l.count(2)
# print(dist)
# print(l)
print(dist[k%g+l.count(1)]+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().rstrip().split()]

l=[0 for i in range(n)]
cnt=0

dist=[]
now=0
while(True):
  
  if l[now]+1==3:
    break
  dist.append(now)

  l[now]+=1
  now=a[now]-1


k=k-l.count(1)
g=l.count(2)
# print(dist)
# print(l)
print(dist[k%g+l.count(1)]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

route = []
town = set()
now = 1

while True:
    now = a[now-1]
    if now in town:
        break
    town.add(now)
    route.append(now)

count = route.index(now)
route = route[count:]
num = (k-count)%len(route)
print(route[num-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [a[i]-1 for i in range(n)]
x = a[a[0]]
l = [0, a[0]]
cnt = 0
while x not in l:
    l.append(x)
    x = a[x]
cnt = len(l)-l.index(x)
loop = l[l.index(x):l.index(x)+cnt]
print(loop[(m-l.index(x)+1)%cnt-1]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

route = []
town = set()
now = 1

while True:
    now = a[now-1]
    if now in town:
        break
    town.add(now)
    route.append(now)
count = route.index(now)
if k <= count:
    print(route[count-1])
else:
    route = route[count:]
    num = (k-count)%len(route)
    print(route[num-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

route = []
now = 1

while True:
    now = a[now-1]
    if now in route:
        break
    route.append(now)
count = route.index(now)
if k <= count:
    print(route[count-1])
else:
    route = route[count:]
    num = (k-count)%len(route)
    print(route[num-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))

for i in range(n):
    a[i] -= 1
    
visited = [-1] * n
now = 0

for i in range(k+1):
    if visited[now] != -1:   #訪れたことがあるか
        loop = i - visited[now]   #ループの大きさ
        k = (k-(i-loop)) % loop
        
        for _ in range(k):
            now = a[now]
        
        break
        
    visited[now] = i
    now = a[now] 
        
print(now + 1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
visit = [0] * (n+1)
a = list(map(int,input().split()))
a.insert(0,0)
visit_list = [[1,1]]
nxt = a[1]
visit[1] = 1
for i in range(2,n+1):
    visit_list.append([i,nxt])
    if visit[nxt] > 0:
        break
    else:
        visit[nxt] = i
    nxt = a[nxt]
#print(i,nxt)
#print(visit_list)
#print(visit_list[0][1])
for j in range(len(visit_list)):
    if visit_list[j][1] == nxt:
        lp = i - j - 1
        st = j
        break
#print(st,lp)
#print((k-st)%lp)
print(visit_list[(k-st)%lp+st][1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [1]
    a = 1
    check = [0] * len(A)
    while True:
        a = A[a - 1]
        if check[a - 1] == 1:
            x = B.index(a)
            roop = B[x:]
            print(roop[(K - x) % len(roop)])
            exit()
        B.append(a)
        check[a - 1] += 1
    if len(B) >= K + 1:
        print(B[K])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [1]
    a = 1
    check = [0] * len(A)
    while True:
        a = A[a - 1]
        if check[a - 1] == 1:
            x = B.index(a)
            roop = B[x:]
            print(roop[(K - x) % len(roop)])
            exit()
        B.append(a)
        check[a - 1] += 1
    if len(B) == K + 1:
        print(B[K])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [1] + [0] * (len(A) - 1)
    for i in range(1,K + 1):
        a = A[B[i - 1] - 1]
        if a in B:
            x = B.index(a)
            y = i - x
            z = (K - x) % y
            print(B[x + z])
            exit()
        B[i] = a
    if len(B) == K + 1:
        print(B[K])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
for i in range(1,K + 1):
    a = A[B[i - 1] - 1]
    if a in B:
        x = B.index(a)
        y = i - x
        z = (K - x) % y
        print(B[x + z])
        exit()
    B.append(a)
if len(B) == K:
    print(B[K - 1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
for i in range(1,K + 1):
    a = A[B[i - 1] - 1]
    if a in B:
        x = B.index(a)
        y = i - x
        z = (K - x) % y
        print(B[x + z])
        break
    B.append(a)
if len(B) == K:
    print(B[K - 1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)
position=[]
unit=[]
position.append(1)
i=0
while True:
  judge=a[position[-1]] in position
  if judge==0:#まだそのノードは未探索
    position.append(a[position[-1]])
    if i==k-1:
      ans=position[-1]
  else:#そのノードは探索済み
    sta=position.index(a[position[-1]])
    end=i+1
    unit=position[sta:end+1]
    if (k-sta+1)%(end-sta)==0:
      ans=unit[-1]
    else:
      ans=unit[(k-sta+1)%(end-sta)-1]
    break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
t=1
for i in range(n):
    b.append(t)
    t=a[t-1]
    if len(set(b))!=len(b):
        break
s=len(b)
h=0
for i in range(s):
    if b[i]==b[s-1]:
        h=i
        break
r=s-h-1
if (k-h+1)%r==0:
    x=r
else:
    x=(k-h+1)%r
print(b[h+x-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lst = [int(i) for i in input().split()]

tele_lst = []
town_set = set()
town = 1
while True:
  if town not in town_set:
    tele_lst.append(town)
    town_set.add(town)
  else:
    break
  town = lst[town - 1]
ind = tele_lst.index(town)
length = len(town_set)
circle = length - ind
#print(ind, length)
#print(tele_lst)
if k < ind:
  town = lst[k]
  print(town)
else:
  k -= ind
  k %= circle
  #print(k)
  town = tele_lst[ind + k]
  print(town)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lst = [int(i) for i in input().split()]

tele_lst = []
town = 1
while True:
  if town not in tele_lst:
    tele_lst.append(town)
  else:
    break
  town = lst[town - 1]
ind = tele_lst.index(town)
length = len(tele_lst)
circle = length - ind
#print(ind, length)
#print(tele_lst)
if k < ind:
  town = lst[k]
  print(town)
else:
  k -= ind
  k %= circle
  town = lst[ind + k]
  print(town)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
visited = [-1] * (n)

cs = -1
i = 0
count = 0
while True:
    visited[i] = count
    count += 1
    i = A[i] - 1
    if visited[i] != -1:
        cs = i
        break
a = (k - count + visited[cs]) % (count+1)
current = cs
#print(count, visited[cs], cs, a)
for i in range(a):
    #print(current)
    current = A[current] -1
print(current+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
c=[0]*(n+1)
c[1]=1
q=[0,1]
while True:
  i=a[q[-1]]
  if c[i]:break
  c[i]=c[q[-1]]+1
  q+=[i]
k-=c[i]-1
t=c[q[-1]]-c[i]+1
print(q[c[i]+k%(t)])

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_cnt = [0] * N
    telepo = [1]
    i = 0
    A_cnt[i] = 1
    roop = 0
    while True:
        if A_cnt[i] > 1:
            roop = telepo.index(A[i]) - 1
            break
        A_cnt[A[i] - 1] += 1
        telepo.append(A[i])
        i = A[i] - 1
    K -= roop
    K %= len(telepo) - roop

    print(telepo[K + roop - 1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_cnt = [0] * N
    telepo = [1]
    i = 0
    A_cnt[i] = 1
    roop = 0
    while True:
        if A_cnt[i] > 1:
            roop = telepo.index(A[i]) - 1
            break
        A_cnt[A[i] - 1] += 1
        telepo.append(A[i])
        i = A[i] - 1
    K -= roop
    K %= len(telepo) - roop - 1

    print(telepo[K + roop])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# †輪廻† する部分の長さがわかれば、そこに至るまでに消費したカウントで割った余りが「†輪廻†に終わりを告げる者（~death warrant~）」になる
# カウントともっておくと二度目の踏破でループの長さが分かりそう
# サンプルを流用しつつKの値を変えることで適当なサンプルケースとする
# 変数ガチャぽくなりそうなので注意

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
count_arr = [0] * n
count = 0

now = 0
loop_length = -1
while True:
    if count == k:
        print(now + 1)
        exit()
    if count_arr[now] != 0:
        loop_length = count - count_arr[now] + 1
        break
    count += 1
    count_arr[now] = count
    now = a[now]

# 真の残り回数
rest = (k - count) % loop_length

# 既にゴールしてると見る場合 ~ you're already dead ~
if rest == 0:
    print(now + 1)
    exit()

#
while rest > 0:
    now = a[now]
    rest -= 1
print(a[now] + 1)

Submission status: Wrong Answer

Solution code:
# カウントと踏破フラグをもっておくと二度目の踏破でループの長さが分かりそう
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
count_arr = [0] * n
count = 0

now = 0
loop_length = -1
while True:
    if count == k:
        print(a[now] + 1)
        exit()
    if count_arr[now] != 0:
        loop_length = count - count_arr[now] + 1
        break
    count += 1
    count_arr[now] = count
    now = a[now]

# 真の残り回数
rest = (k - count) % loop_length

# 既にゴールしてると見る場合
if rest == 0:
    print(now + 1)
    exit()

while rest > 0:
    rest -= 1
    if rest == 0:
        break
    now = a[now]
print(a[now] + 1)
# 727202214173249352

Submission status: Wrong Answer

Solution code:
# カウントと踏破フラグをもっておくと二度目の踏破でループの長さが分かりそう
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
count_arr = [0] * n
count = 0

now = 0
loop_length = -1
while True:
    if count == k:
        print(a[now] + 1)
        exit()
    if count_arr[now] != 0:
        loop_length = count - count_arr[now] + 1
        break
    count += 1
    count_arr[now] = count
    now = a[now]

# 真の残り回数
rest = (k - count) % loop_length

# 既にゴールしてると見る場合
if rest == 0:
    print(now + 1)
    exit()

while rest > 0:
    print(f"now = {now}(next = {a[now]})")
    rest -= 1
    if rest == 0:
        break
    now = a[now]
print(a[now] + 1)
# 727202214173249352

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]

c = 1
for i in range(n):
    c = a[c]
    if c not in b:
        b.append(c)
        if i == k-1: print(c)
        sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = []

c = 1
for i in range(k):
    c = a[c]
    if c not in b:
        b.append(c)
        if i == k-1: print(c); sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

kk = (k-sn) % bn
print(b[idx+kk-1])

Submission status: Wrong Answer

Solution code:
# 無限ループには入る前aこ
# 無限ループ内のb個

N, K = map(int, input().split())
A = list(map(int, input().split()))

a = [Ai-1 for Ai in A]


visited = [0]*N
visited[0] = 1
p = 0
l = [0]
loop_start = None
while True:
    p = a[p]
    if visited[p]:
        loop_start = l.index(p)
        break
    visited[p] = 1
    # print(p, visited)
    l.append(p)

# print(l, loop_start, K)

if K < loop_start:
    print(l[K])
else:
    print(l[loop_start + (K-loop_start)%(len(l)-loop_start)]+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

a = [Ai-1 for Ai in A]


visited = [0]*N
visited[0] = 1
p = 0
l = [0]
loop_start = None
while True:
    p = a[p]
    if visited[p]:
        loop_start = l.index(p)
        break
    visited[p] = 1
    # print(p, visited)
    l.append(p)

# print(l, loop_start, K)

if K <= loop_start:
    print(l[K])
else:
    print(l[loop_start + (K-loop_start)%(len(l)-loop_start)]+1)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

A_={}
for a_idx,a in enumerate(A):
    A_[a_idx+1] = a

visit={}
first={}
for n in range(N):
    visit[n+1]=0
    first[n+1]=-1
    
v=1
Loop=[]
for n in range(2*N):   
    Loop.append(v)
    if visit[v] == 0:
        first[v] = n
    visit[v]+=1
#     print(v,visit)
    if visit[v] == 2:
        break
        
    v=A_[v]

ans_idx=(K-first[v])%(n-first[v])
print(Loop[first[v]:n][ans_idx])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

b = 0
r = k + 1
xs = [0] * n
seen = [-1] * n
seen[0] = 0
p = 1
for i in range(k):
    p = a[p - 1]
    xs[i] = p
    if seen[p - 1] != -1:
        b = seen[p - 1]
        r = i + 1 - b
        print(xs[b + (k - b) % r - 1])
        exit()
    seen[p - 1] = i + 1
else:
    print(p)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

r = 0
p = 0
seen = {0}
for i in range(k):
    x = a[p] - 1
    if x in seen:
        break
    p = x
    seen.add(p)
    r = i + 1
ans = 0
for i in range(r):
    ans = a[ans] - 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
f = [int(x)-1 for x in input().split()]

def tortoise_and_hare(s,f):
    tortoise = f[s]
    hare = f[f[s]]

    while tortoise != hare:
        tortoise = f[tortoise]
        hare = f[f[hare]]

    rho = 0
    tortoise = s
    while tortoise != hare:
        tortoise = f[tortoise]
        hare = f[hare]
        rho += 1

    lamb = 1
    hare = f[hare]

    while tortoise != hare:
        hare = f[hare]
        lamb += 1

    return rho,lamb

rho, lamb = tortoise_and_hare(0,f)
print(rho,lamb)
if k <= rho:
    s = 0
    for i in range(k):
        s = f[s]
else:
    s = 0
    for i in range(rho):
        s = f[s]
    k = (k-rho)%lamb
    for i in range(k):
        s = f[s]

print(s+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
A = [a-1 for a in A]


seen = defaultdict(list)
count = 0
pos = 0
seen[pos].append(count)

while True:
    pos = A[pos]
    count += 1
    seen[pos].append(count)
    if len(seen[pos]) == 2:
        head = seen[pos][0]
        loop = count - head
        break


if K < head:
    for key, value in seen.items():
        if value == K:
            print(A[key]+1)
            exit()

else:
    K = K - head
    res = K % loop
    for i in range(res):
        pos = A[pos]

    print(pos+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
A = [a-1 for a in A]


seen = defaultdict(list)
count = 0
next_ = 0
seen[next_].append(count)

while True:
    next_ = A[next_]
    count += 1
    seen[next_].append(count)
    if len(seen[next_]) == 2:
        head = seen[next_][0]
        loop = count - head
        break


if K < head:
    for key, value in seen.items():
        if value == K:
            print(A[key]+1)
            exit()

else:
    K = K - head
    res = K % loop
    print(A[head + res]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int,input().split())
tele = list(map(int, input().split()))

#A1から順にワープした時の経由順
now = 0
goal,loop,visit = [],[],[0]*N

while visit[now]!=2:

  if visit[now]==0:
    goal.append(now)
  else:
    loop.append(now)
    
  visit[now] += 1
  now = tele[now]-1

if len(goal)>K:
  print(goal[K]+1)
amari = len(goal)-len(loop)
print(loop[(K-amari)%len(loop)]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int,input().split())
tele = list(map(int, input().split()))

#A1から順にワープした時の経由順
now = 0
goal,loop,visit = [],[],[0]*N

while visit[now]!=2:

  if visit[now]==0:
    goal.append(now)
  else:
    loop.append(now)
    
  visit[now] += 1
  now = tele[now]-1

amari = len(goal)-len(loop)
print(loop[(K-amari)%len(loop)]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int,input().split())
tele = list(map(int, input().split()))

#A1から順にワープした時の経由順
next_,goal,visit = 1,[],[0]*N
while visit[next_-1]<2:
  goal.append(next_)
  next_ = tele[next_-1]
  visit[next_-1] += 1
  
i,loop = -1,[]
while goal[i]!=next_:
  loop.insert(0,goal[i])
  #print(goal[i])
  i-=1

loop.insert(0,next_)
amari = len(goal)-len(loop)
print(loop[(K-amari)%len(loop)])

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int,input().split())
tele = list(map(int, input().split()))

#A1から順にワープした時の経由順
next_,goal = 1,[]
while goal.count(next_)<1:
  goal.append(next_)
  next_ = tele[next_-1]
  #print(goal.count(next_))
  
i,loop = -1,[]
while goal[i]!=next_:
  loop.insert(0,goal[i])
  #print(goal[i])
  i-=1

loop.insert(0,next_)
amari = len(goal)-len(loop)
print(loop[(K-amari)%len(loop)])

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
tele = list(map(int, input().split()))

#A1から順にワープした時の経由順
next_,loop,goal = 1,[],[]
for n in range(N):
  next_ = tele[next_-1]
  if next_ in goal:
    loop = goal[goal.index(next_):len(goal)]
    break
  goal.append(next_)
  
amari = len(goal)-len(loop)
print(loop[(K-amari)%len(loop)-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
cycle=[1]
i=1
while True:
  i=l[i-1]
  if i in cycle:
    cycle=cycle[cycle.index(i):]
    break
  else:
    cycle+=[i]
print(cycle[(m-i)%len(cycle)])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
cycle=[1]
i=1
while True:
  i=l[i-1]
  if not i in cycle: 
    cycle+=[i]
  else:
    i=cycle.index(i)
    cycle=cycle[i:]
    break
m=m-i
m=m%len(cycle)
print(cycle[m])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
cycle=[1]
i=1
while True:
  if not l[i-1] in cycle: 
    cycle+=[l[i-1]]
    i=l[i-1]
  else:
    i=l[i-1]
    i=cycle.index(i)
    cycle=cycle[i:]
    break
m=m-i
m=m%len(cycle)
print(cycle[m])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
cycle=[1]
i=1
while len(cycle)<n:
  if not l[i-1] in cycle: 
    cycle+=[l[i-1]]
    i=l[i-1]
  else:
    i=l[i-1]
    i=cycle.index(i)
    cycle=cycle[i:len(cycle)]
    break
m=m-i
m=m%len(cycle)
print(cycle[m])

Submission status: Wrong Answer

Solution code:
import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = [1]
next_town = 1
for i in range(N):
    next_town = A[next_town - 1]
    if next_town in teleport:
        dupulicate_town = next_town
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        break
    else:
        teleport.append(next_town)


if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])

Submission status: Wrong Answer

Solution code:
N, K= map(int, input().split())
A = [0] + list(map(lambda a: int(a), input().split()))

now = 1
loop = []
checker = set()
loop.append(now)
checker.add(now)
while True:
    nxt = A[now]
    loop.append(nxt)
    checker.add(nxt)
    now = nxt
    if len(loop) != len(checker):
        break

end = loop[-1]
first_end = loop.index(end)
loop_circle = len(loop)-first_end-1

loopy = loop[first_end:-1]
if len(loopy) > K:
    print(loopy[K])
    quit()
num = K-first_end
ans = loopy[(num%loop_circle)]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K= map(int, input().split())
A = [0] + list(map(lambda a: int(a), input().split()))

now = 1
loop = []
checker = set()
loop.append(now)
checker.add(now)
while True:
    nxt = A[now]
    loop.append(nxt)
    checker.add(nxt)
    now = nxt
    if len(loop) != len(checker):
        break
end = loop[-1]
first_end = loop.index(end)
loop_circle = len(loop)-first_end-1
loopy = loop[first_end:-1]
num = K-first_end
if num<0:
    print(A[K])
    quit()
ans = loopy[(num%loop_circle)]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K= map(int, input().split())
A = [0] + list(map(lambda a: int(a), input().split()))

now = 1
loop = []
checker = set()
loop.append(now)
checker.add(now)
while True:
    nxt = A[now]
    loop.append(nxt)
    checker.add(nxt)
    now = nxt
    if len(loop) != len(checker):
        break
end = loop[-1]
first_end = loop.index(end)
loop_circle = len(loop)-first_end-1
loopy = loop[first_end:-1]
num = K-first_end
ans = loopy[(num%loop_circle)]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K= map(int, input().split())
A = [0] + list(map(lambda a: int(a), input().split()))

now = 1
loop = []
checker = set()
loop.append(now)
checker.add(now)
while True:
    nxt = A[now]
    loop.append(nxt)
    checker.add(nxt)
    now = nxt
    if len(loop) != len(checker):
        break
print(loop)
end = loop[-1]
first_end = loop.index(end)
loop_circle = len(loop)-first_end-1
loopy = loop[first_end:-1]
print(loopy)
print(loop_circle, first_end)
num = K-first_end
ans = loopy[(num%loop_circle)]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]



#いまいるところ,
#listとnが与えられたときn回テレポートしたところを出力する
def now_place(li,n):
    now = 1
    for i in range(n):
        now = li[now-1]
    return now




n,k = MI()
a = LI()
#薫り高い町を求めよう
#訪れた町をリストに入れていって重複が出てきたらそこが薫り高い町
#そこまでのstep数も数える
cnt = 0
place=[1]
s = a[1-1]
for i in range(n):
    if a[s-1] in place:
        town = a[s-1]
        cnt = i - 1
        break
    place.append(a[s-1])
    s = a[s-1]
#周期を求める
t = 0
now = town
for i in range(n):
    t += 1
    now = a[now-1]
    if now == town:
        break
if k <= cnt:
  print(now_place(a,k))
else:
  print(now_place(a,cnt+(k-cnt)%t))