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: Accepted

Solution code:
n, k = map(int, input().strip().split())
L = list(map(int, input().strip().split()))
L = [v - 1 for v in L]

seen = set()
cur = 0
untillBackToIntersec = 0

while cur not in seen:
    seen.add(cur)
    untillBackToIntersec += 1
    cur = L[cur]

intersec = cur
cur = 0
beforeLoop = 0

while cur != intersec:
    cur = L[cur]
    beforeLoop += 1
if k<=beforeLoop:
    proceed=k
else:
    loopSize = untillBackToIntersec - beforeLoop
    proceed=(k - beforeLoop) % (loopSize) + beforeLoop
ans = 0

for _ in range(proceed):
    ans = L[ans]

print(ans + 1)

Submission status: Accepted

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

res=[1,a[0]]
d=set(res)

end=0
ans=0

while True:
    if i>n-1:
      break
    
    i=a[i]-1
    t=a[i]
    if t not in d:
        res.append(t)
        d.add(t)
    else:
        end=i
        break
l=len(res)
s=res.index(a[end])
r=l-s
if k<l:
    print(res[k])
else:
    k-=s
    ans=k%r + s
    print(res[ans])

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**8)
import numpy as np
done=np.array([0]*N)
X=[0]*2
L=[]
F=[True]
def dfs(start, steps):
    done[start-1]+=1
    L.append(start)
    if done[start-1]==3:
        X[1]=steps
        return
    elif done[start-1]==2 and F[0]:
        X[0]=steps
        F[0]=False
    nex=A[start-1]
    dfs(nex, steps+1)
dfs(1,0)
#print(done)
#print(X)
#print(L)
first=L[:X[0]-(X[1]-X[0])]
sec=L[X[0]-(X[1]-X[0]):X[0]-(X[1]-X[0])+(X[1]-X[0])]
#print(first, sec)
if len(first)==0:
    first=sec
if K+1<=len(first):
    print(first[K])
else:
    K=K-len(first)
    print(sec[(K%len(sec))])

Submission status: Accepted

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

arr = [-1]*n
next_town = 0
arr[0] = 0
flag = False
for i in range(1, k+1):
    #print(next_town+1)
    next_town = a[next_town] - 1
    if arr[next_town] >= 0:
        flag = True
        x = i - arr[next_town]
        l = arr[next_town]
        break
    else:
        arr[next_town] = i
#print(flag, x, k%x)
if flag == False:
    print(next_town+1)
else:
    for i in range((k-l)%x):
        #print(next_town+1)
        next_town = a[next_town] - 1

    print(next_town+1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
from collections import deque
d=deque([0])
li=[0]*n
c=1
lis=[]
for i in range(n+1):
  now=d.pop()
  ne=l[now]
  li[now]=c
  lis.append(now)
  if li[ne-1]!=0:
    z=ne-1
    break
  else:
    d.append(ne-1)
x=lis.index(z)
if m<x+1:
  print(lis[m]+1)
else:
  print(lis[(m-x)%(len(lis)-x)+x]+1)

Submission status: Accepted

Solution code:
def change(a):
    return int(a) - 1


n, k = map(int, input().split())

ls = list(map(change, input().split()))
visited = [False] * n
visited[0] = True
i = 0
while True:
    if not visited[ls[i]]:
        visited[ls[i]] = True
        i = ls[i]
    else:
        end = ls[i]
        break
loop = 0
i = end
while True:
    if ls[i] == end:
        loop += 1
        break
    else:
        i = ls[i]
        loop += 1

i = 0
till_loop = 0
while True:
    if ls[i] == end:
        till_loop += 1
        break
    else:
        i = ls[i]
        till_loop += 1
if till_loop + loop <= k:
    k -= till_loop
    k %= loop
    i = end
    while k > 0:
        i = ls[i]
        k -= 1
    print(i+1)
else:
    i = 0
    while k > 0:
        i = ls[i]
        k -= 1
    print(i+1)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
    
al = [1]
num2ind = {1:0}
for i in range(K):
    ne = A[al[-1]-1]
    al.append(ne)
    if ne in num2ind:
        tar = num2ind[ne]
        break
    num2ind[ne] = i+1
    
ne = i+1
if K<=len(al):
    print(al[K])
else:
    K-=tar
    K%=(ne-tar)
    print(al[tar+K])

Submission status: Accepted

Solution code:
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*len(A)

i = 0
c = 0
while K > 0:
    if B[i] == 0:
        B[i] = c
        j = A[i] - 1
        i = j
        K -= 1
        c += 1
    else:
        x = c - B[i]
        K = K % x
        B = [0]*len(A)

print(j + 1)

Submission status: Accepted

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

if k <= n:
    takahashi = 0
    for _ in range(k):
        takahashi = a[takahashi] - 1
    print(takahashi + 1)
else:
    start = 0
    takahashi = start
    trajectory = [takahashi]
    loop_start = -1
    loop_end = -1
    visited = [False] * n
    visited[0] = True
    for i in range(n):
        takahashi = a[takahashi] - 1
        if visited[takahashi]:
            loop_start = trajectory.index(takahashi)
            break
        visited[takahashi] = True
        trajectory.append(takahashi)
    print(trajectory[loop_start:][(k - loop_start) % (i + 1 - loop_start)] + 1)

Submission status: Accepted

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

visited = [0] * N
cnt = 0
i = 0
loop = 0
while True:
    visited[i] = cnt
    i = A[i] - 1
    cnt += 1
    if visited[i] > 0 or i == 0:
        loop = cnt - visited[i]
        break

m = 0
if K < visited[i]:
    m = K
    i = 0
else:
    m = (K - visited[i]) % loop

for _ in range(m):
    i = A[i] - 1
print(i+1)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    s = input().rstrip().split(' ')
    N, K = int(s[0]), int(s[1])
    s = input().rstrip().split(' ')
    A = [int(elem) for elem in s]

    route_until_loop = []
    route_dict = {}
    loop = []
    pos = 0
    count = 0
    while True:
        route_until_loop.append(pos)
        route_dict[pos] = count
        count += 1
        # go next
        pos = A[pos]-1
        if pos in route_dict.keys():
            break;

    loop = route_until_loop[route_dict[pos]:]
    route_until_loop = route_until_loop[:route_dict[pos]]

    #print(route_until_loop)
    #print(loop)

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

Submission status: Accepted

Solution code:
n,k=(int(i) for i in input().split())
r=[0 for i in range(n)]
l=[int(i) for i in input().split()]
wazap=[]
count=1
saver=None
temp=0
while r[temp]==0:
  r[temp]=count
  wazap.append(temp)
  temp=l[temp]-1
start=l[wazap[-1]]
left=None
for i in range(len(wazap)):
  if wazap[i]==start-1:
    left=i
    break
loop=len(wazap)-left
if k<left:
  print(wazap[k]+1)
else:
  print(wazap[(k-left)%loop+left]+1)

Submission status: Accepted

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

move_dic = {1:0}
move_list = [1]
pre = A[0]
counter = 0
while True:
    if pre in move_dic:
        loopstart = move_dic[pre]
        loop = move_list[loopstart:]
        init_len = len(move_list)
        loop_len = len(loop)
        break
    else:
        counter += 1
        move_dic[pre] = counter
        move_list.append(pre)
        pre = A[pre - 1]

if K >= init_len:
    ans = (K - init_len) % loop_len
    print(loop[ans])
else:
    print(move_list[K])

Submission status: Accepted

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(N):
    A[i] -= 1
    
visited = [-1] * N
visited[0] = 0
ret = [0]
next_ = A[0]
roop_start = 10 ** 9 + 7

for i in range(1, K + 1):
    if visited[next_] != -1:
        roop_start = visited[next_]
        break
    ret.append(next_)
    visited[next_] = i
    next_ = A[next_]
    
if K <= roop_start:
    print(ret[K] + 1)
else:
    roop_length = len(ret) - roop_start
    mod = (K - roop_start) % roop_length
    print(ret[roop_start + mod] + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for i in range(n)]
b[0] += 1
i = 0
ans = 0
c = a[0]
while True:
    b[c-1] += 1
    i += 1
    if i == k:
        print(c)
        exit()
    if b[c-1] > 1:
        ans = c
        break
    c = a[c-1]
c = a[0]
j = 0
while True:
    j+=1
    if c == ans:
        break
    c = a[c-1]
if c == 1:
    j = 0
k -= j
k %= (i-j)
for i in range(k):
    c = a[c-1]
print(c)

Submission status: Accepted

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

visited = set()
current = 0
answer = 0
count = 0
while current not in visited and count < K:
    visited.add(current)
    count += 1
    current = A[current]
    answer = current

if count == K:
    print(answer + 1)
    exit(0)

# print(count)
start = A[current]
ary = [start]
loop_size = 1
while start != current:
    loop_size += 1
    start = A[start]
    ary.append(start)

# print(ary)
# print('loop_size', loop_size)
print(ary[(K - count) % loop_size - 1] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
toujou = [0] * N
toujou[0] = 1
kosuu = 1
tadoru = [1]
pin = 1
tmp = 1
while pin == 1:
    tmp = A[tmp-1]
    toujou[tmp-1] += 1
    if toujou[tmp - 1] == 2:
            break
    else:
        tadoru.append(tmp)
        kosuu += 1

loop_start = tadoru.index(tmp)
loop = kosuu - loop_start
if K < kosuu:
    print(tadoru[K])
else:
    K = K - loop_start
    a = K % loop
    print(tadoru[loop_start + a])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
N,K = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

loop = []
pre = []
visited = set()

def dfs(index,now):
    global pre
    global loop
    loop.append(now)
    if now in visited:
        for left in range(len(loop)):
            if now == loop[left]:
                break
        pre = loop[:left]
        loop = loop[left:index]
        return
    else:
        visited.add(now)
        dfs(index+1,A[now-1])
dfs(0,1)

if len(pre) > K:
    print(pre[K])
else:
    K-=len(pre)
    print(loop[K%len(loop)])

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

for i in range(N):
    A[i] -= 1

visited = set()
visited.add(0)
trace = []
cur = 0
while True:
    trace.append(cur)
    if A[cur] in visited:
        cur = A[cur]
        break
    visited.add(A[cur])
    cur = A[cur]

pre = 0
for i, a in enumerate(trace):
    if a == cur:
        pre = i

loop = len(trace) - pre

if K <= pre:
    ans = trace[K]
else:
    if loop == 0:
        ans = trace[pre::][0]
    else:
        r = (K - pre) % loop
        ans = trace[pre::][r]

print(ans + 1)

Submission status: Accepted

Solution code:
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
newlist = [1,A[0]]
num = A[0] - 1
ans = [0]*N
ans[0] = 1
ans[A[0]-1] = 1
b = 0
c = 0
r = 0
for i in range(K):
    if(ans[A[num]-1] == 1):
        b = A[num]
        break
    newlist.append(A[num])
    ans[A[num]-1] = 1
    num = A[num]-1
for i in range (len(newlist)):
    if(newlist[i] == b):
        c = i
r = len(newlist)-c
a = (K-c)%r
print(newlist[c+a])

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
memo = [-1]*(N+1)
junban = deque()
A = [0]+list(map(int, input().split()))
i = 0
x = 1
while memo[x] < 0:
  junban.append(x)
  memo[x] = i
  x = A[x]
  i += 1
T = i-memo[x]
if K < i:
  print(junban[K])
else:
  print(list(junban)[memo[x]:][(K-memo[x])%T])

Submission status: Accepted

Solution code:
from sys import stdin

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [0] + A
    la = []
    now = 1
    visited = [False] * (N + 1)
    last = None
    while True:
        if visited[now]:
            last = now
            break
        la.append(now)
        visited[now] = True
        now = A[now]

    ans = None
    if len(la) > K:
        ans = la[K]
    else:
        period = len(la) - la.index(last)
        lai = la.index(last)
        if lai > 0:
            K -= lai
        rem = K % period
        ans = la[lai + rem]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+[int(j) for j in input().split()]
l=[-1]*(n+1)
ll=[]
i=1
idx=0
while True:
    if l[i]==-1:
        l[i]=idx
    else:
        ll.append(i)
        break
    ll.append(i)
    i=a[i]
    idx+=1

p=ll[-1]
nl=ll[l[p]:-1]
ml=ll[:l[p]]
n,m=len(nl),len(ml)
if k<m:
    print(ml[k])
elif nl==[]:
    print(p)
    exit()
else:
    print(nl[(k-m)%n])

Submission status: Accepted

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

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

now = 1

d = []
set_d = set()

while True:
    if A[now-1] in set_d:
        i = d.index(A[now-1])
        check = d[i:]
        break
    now = A[now-1]
    d.append(now)
    set_d.add(now)

    if len(set_d) >= K:
        break

if K <= len(set_d):
    print(d[K-1])
else:
    K -= (len(set_d)-len(check))
    K = K % len(check)
    print(check[K-1])

Submission status: Accepted

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

A.insert(0,-1)

visited = [False]*(N+1)
now_town = 1
to_start = 0

while 1:
    if visited[now_town] == True:
        break
    else:
        visited[now_town] = True
        now_town = A[now_town]
        to_start += 1

roop_start = now_town

now_town = roop_start
roop = 0
while 1:
    roop += 1
    now_town = A[now_town]
    if now_town == roop_start:
        break

to_start -= roop

if K <= to_start:
    now_town = 1
    for i in range(K):
        now_town = A[now_town]
    print(now_town)
else:
    K -= to_start
    K %= roop
    now_town = roop_start
    for i in range(K):
        now_town = A[now_town]
    print(now_town)

Submission status: Accepted

Solution code:
import sys
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()))
dict = [-1] * (n + 1)
now = a[0]
dict[0] = 0
for i in range(1, n * 2):
    if i == k:
        print(now)
        exit()
    now = a[now - 1]
    if dict[now] != -1:
        k -= (i + 1)
        k %= (i - dict[now])
        break
    else:
        dict[now] = i
for i in range(k):
    now = a[now - 1]
print(now)

Submission status: Accepted

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


def solve(N, K, A):
    visited = [1]
    vset = set()
    vset.add(1)
    now = 1
    b = 0
    l = 0
    for _ in range(N):
        now = A[now - 1]
        if now in vset:
            b = visited.index(now)
            l = len(visited) - b
            break
        else:
            visited.append(now)
            vset.add(now)
    if K >= b:
        x = (K - b) % l
        print(visited[b + x])
    else:
        print(visited[K])
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    d = []
    d_set = set()
    s = 1
    for _ in range(N):
        if s in d_set:
            if K < len(d):
                return print(d[K])
            idx = d.index(s)
            K -= idx
            d = d[idx:]
            break
        d.append(s)
        d_set.add(s)
        s = A[s-1]

    # print(idx, d)
    K %= len(d)
    print(d[K])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

l = []
c = 1
l2 = [0 for _ in range(n)]
for _ in range(n):
    c = a[c - 1]
    if len(l) + 1 == k:
        print(c)
        break
    elif l2[c - 1] == 1:
        i = l.index(c)
        l2 = l[i:]
        print(l2[(k - i) % len(l2) - 1])
        break
    else:
        l.append(c)
        l2[c - 1] = 1

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=set()
l=list()
s.add(0)
d=dict()
ind=0
l.append(0)
d[0]=0
s.add(0)
ind+=1
while(True):
    if a[l[-1]]-1 in s:
        break
    d[a[l[-1]]-1]=ind
    s.add(a[l[-1]]-1)
    l.append(a[l[-1]]-1)
    ind+=1
# print(d)
ind=d[a[l[-1]]-1]
# print(ind,a[l[-1]]-1)
if k==len(l):
    r=0
    print(l[ind+r]+1)
elif k>len(l):
    r=(k-len(l))%(len(l)-ind)
    print(l[ind+r]+1)
else:
    r=k
    print(l[r]+1)
# print(l)
# print(r)

Submission status: Accepted

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

towns = [0] * n
i = 0
cnt = 1
towns[0] = cnt
nums = [1]
while True:
    cnt += 1
    i = a[i] - 1
    if towns[i] == 0:
        towns[i] = cnt
        nums.append(i + 1)
    else:
        s_loop = nums.index(i + 1)
        m = len(nums)
        l = m - s_loop
        break

if k < len(nums):
    print(nums[k])
else:
    k -= m - 1
    k = (k - 1) % l
    print(nums[s_loop + k])

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().split()]
p=[(int(x)-1) for x in input().split()]
alp=[0 for _ in range(n)]
a=[0]
i=0
alp[0]=1
while alp[p[i]]==0:
  a.append(p[i])
  alp[p[i]]=1
  i=p[i]
l=a.index(p[i])
if k<=l: print(1+a[k])
else: print(1+a[l+(k-l)%(len(a)-l)])

Submission status: Accepted

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

# 戻ってくるまでのリスト
R=[]
Rs=set()
Now=1
cnt=0
for i in range(N):
    if Now in Rs:
        Start=R.index(Now)
        End = cnt
        break
    else:
        R.append(Now)
        Rs.add(Now)
        Now=A[Now-1]
        cnt+=1

if K < End:
    ans=R[K]
else:
    key=Start+(K-Start)%(End-Start)
    ans=R[key]

print(ans)
#print(Start,End)
#print(R)
#Start+K(End-Start)

Submission status: Accepted

Solution code:
line1 = input().split()
n = int(line1[0])
k = int(line1[1])
a = [int(ai) for ai in input().split()]

route = [0]
use = {0}
for j in range(k):
  now = a[route[j]] - 1
  if now in use:
    break
  else:
    route.append(now)
    use.add(now)

l_start = route.index(now)
print(route[l_start + ((k - l_start) % (len(route) - l_start))] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(n)-1 for n in input().split()]

pos, root, cnt, lst = 0, {}, 0, []
while True:
    if cnt == K:
        ans = pos + 1
        break
    if pos in root:
        ans = lst[root[pos] + (K-root[pos]) % (cnt-root[pos])] + 1
        break
    root[pos] = cnt
    lst.append(pos)
    cnt += 1
    pos = A[pos]

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
tele = [0] * N
for i in range(N):
    tele[i] = A[i] - 1
now = 0
cnt = 0
exp = [False] * N
period = 0
loop = False
start = -1
while cnt < K:
    exp[now] = True
    now = tele[now]
    cnt += 1
    if loop:
        period += 1
        if now == start:
            loop = False
            cnt = K - ((K - cnt) % period)
    if exp[now] and (not loop):
        loop = True
        start = now
    # print(now, exp, cnt, period, start)
print(now+1)

Submission status: Accepted

Solution code:
import collections
 
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
a = [int(i)-1 for i in a]
 
ex = collections.defaultdict(lambda:-1)
step=1
cur=0
ex[0]=0
while 1:
    if ex[a[cur]]!=-1:
        cycle = step-ex[a[cur]]
        k-=ex[a[cur]]-1
        #print(k%cycle)
        break
    else:
        if step==k:
            print(a[cur]+1)
            exit()
        ex[a[cur]]=step
        cur=a[cur]
    step+=1

#print(ex,k%cycle)
for i in range(k%cycle):
    cur = a[cur]
print(cur+1)

Submission status: Accepted

Solution code:
N, K = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]

f = {}

def town(k):
    t = 1
    i = 0
    while i < k:
        f[t] = i
        t = A[t-1]
        i += 1

        if t in f:
            j = f[t]
            r = i - j
            k = i + (k - i) % r
    return t

print(town(K))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
al = list(map(int, input().split()))
al = [a-1 for a in al]
used = [0]*n
first = [0]*n
step = 0
used[0] = 1
now = 0
for i in range(k):
    step += 1
    get = al[now]
    if used[get] == 0:
        first[get] = step
        used[get] = 1
        now = get
    else:
        dif = step-first[get]
        nokori = (k-step) % dif
        now = get
        for j in range(nokori):
            get = al[now]
            now = get
        print(now+1)
        exit()
print(now+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = 1
c = [-1]*n
c[0] = 0
for i in range(n):
    b = a[b-1]
    if c[b-1] == -1:
        c[b-1] = i+1
    else:
        d = i+1-c[b-1]
        e = c[b-1]
        break;
b = 1
for i in range(min(k, e+(k-e)%d)):
    b = a[b-1]
print(b)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

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

    graph = [0] * (N+1)
    for i in range(N+1): #1-indexed
        f = i
        t = A[i-1]
        graph[f] = t


    def solve():
        visited_set = set([])
        visited = []
        stack = deque([1])
        x = 1
        count = 0
        while len(stack) > 0:
            x = stack.pop()
            if x in visited_set:
                break

            visited_set.add(x)
            visited.append(x)
            stack.append(graph[x])
            count += 1

            if count == K:
                print(stack.pop())
                exit()

        loop_head = x
        head_index = visited.index(loop_head)
        loop_len = len(visited) - head_index

        r = (K-head_index)%loop_len
        print(visited[head_index:][r])



    solve()


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        p = q.popleft()
        if dist[a[p]] == -1:
            dist[a[p]] = dist[p] + 1
            q.append(a[p])
        else:
            return [dist[a[p]], dist[p] + 1]

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)
dist = [-1] * (n + 1)
x = bfs(1)
y = [0, x[1] - x[0], k - x[0]]
l = y[2] % y[1]
ans = l + x[0]
if k <= x[0]:
    ans = k
for i in range(1, n + 1):
    if dist[i] == ans:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x)-1, input().split()))

    visited = [0] * N
    way = []
    now = 0

    while True:
        if visited[now] == 1: break
        if K == 0: return print(now+1)
        visited[now] = 1
        way.append(now)
        destination = A[now]
        K -= 1
        now = destination

    loop = way[way.index(now):len(way)]
    # print(loop)
    # print(K)
    print(loop[K%len(loop)]+1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
T = set([0])  # 0-indexed

c = 0  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
    else:
        break
C = deque([c])
T = set([c])  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
        C.append(c)
    else:
        break
c2 = 0  # 0-indexed
S = deque([0])
for i in range(N + 1):
    c2 = A[c2] - 1
    if c2 == c:
        break
    else:
        S.append(c2)
# print('C', C)
# print('S', S)
# print('len(C), len(S)', len(C), len(S))

if C[0] == 0:
    mod = K % len(C)
    ans = C[mod]
else:
    if len(S) > K:
        ans = S[K]
    else:
        mod = (K - len(S)) % len(C)
        ans = C[mod]
print(ans + 1)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
lis = list(map(int, input().split()))
lis_cost = [-1]*N
lis_root = [1]

s = 1
cost = -1
while True:
    g = lis[s-1]
    cost += 1
    if lis_cost[s-1] == -1:
        lis_cost[s-1] = cost
        s = g
        lis_root.append(g)
    else:
        break
    #print(lis_cost)
    
#print(cost,s) # cost回目のジャンプでs番目に着いた

cost_loop = cost-lis_cost[s-1]
cost_prev = lis_cost[s-1]
lis_root_loop = lis_root[cost_prev:-1]
lis_root_prev = lis_root[:cost_prev]
#print(cost_loop,cost_prev,lis_root_prev)

if cost_prev <= K:
    q = (K-cost_prev+1)%len(lis_root_loop)
    print(lis_root_loop[q-1])
else:
    print(lis_root_prev[K])

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################

def main():
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    for a in range(len(A)):
        A[a]-=1
    now=0

    if K<=N:
        for a in range(K):
            now=A[now]
        print(now+1)
    else:
        V=set([0])
        u=None
        cnt=None
        heiro=[]
        history=[0]
        for a in range(N+100):
            now=A[now]
            if now in V:
                u=now
                cnt=a+1
                break
            V.add(now)
            history.append(now)
        for a in range(len(V)-1,-1,-1):
            heiro.append(history[a])
            if history[a]==u:
                break
        heiro.reverse()
        cnt-=len(heiro)
        if K<=cnt:
            print(history[K]+1)
        else:
            K-=cnt
            n=len(heiro)
            K%=n
            print(heiro[K]+1)


main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
i=0
cnt=0
lcnt=0
sl=[0]*n
for p in range(k):
  if sl[i]==0:
    sl[i]=1
    i=l[i]-1
    cnt+=1
  elif sl[i]==1:
    sl[i]=2
    lcnt+=1
    i=l[i]-1
  else:
    c=(k-cnt)%lcnt
    if c!=0:
      for tmp in range(c):
        i=l[i]-1
    break
print(i+1)