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().split())

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

ansl = []
used = [0 for i in range(n+1)]
now = 0
while True:
    if used[now] == 1:
        break
    ansl.append(now)
    used[now] = 1
    now = al[now] - 1

l = len(ansl)
last = ansl.index(now)
loop = ansl[last:]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,k = map(int, input().split())
a = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n):
    adjacent_list[i+1].append(a[i])
finished = set()
route = []
def dfs(node):
    finished.add(node)
    route.append(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
if len(route) > k:
    print(route[k])
else:
    index = route.index(adjacent_list[route[-1]][0])
    k -= index
    route = route[index:]
    print(route[k % len(route)])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
check=[False]*n
now=0
order=[]
while True:
    now=a[now]-1
    order.append(now)
    if check[now]:
        break
    else:
        check[now]=True
order2=[]
now=order[-1]
while True:
    now=a[now]-1
    order2.append(now)
    if now==order[-1]:
        break
if k<=len(order):
    print(order[k-1]+1)
else:
    k-=len(order)
    x=k%len(order2)
    print(order2[x-1]+1)

Submission status: Accepted

Solution code:
#from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


yes = "Yes"
no = "No"




def main():
    n,k = mi()
    a = li()
    for i in range(n):
        a[i]-=1
    tmp = 0
    if a[0] == 0:
        print(1)
        exit()

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

    while donelist[tmp]==0:
        donelist[tmp] = cnt
        tmp = a[tmp]
        cnt+=1
        if cnt == k:
            print(tmp+1)
            exit()
    anstmp = k-donelist[tmp]
    anstmp%=cnt-donelist[tmp]
    for i in range(anstmp):
        tmp = a[tmp]
    print(tmp+1)







main()

Submission status: Accepted

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

for i in range(n):
    a[i]-=1

#print(a)

ever=[False]*n

ever[0]=True

now=0
saisho=[0]
for i in range(n):
    now=a[now]
    if(not ever[now]):
        saisho.append(now)
        ever[now]=True
    else:
        break

#print(saisho)

roop=[]

roop.append(a[saisho[-1]])
now=roop[0]
for i in range(n):
    now=a[now]
    if(now!=roop[0]):
        roop.append(now)
    else:
        break

#print(roop)

s=len(saisho)
r=len(roop)

if(k<s):
    print(saisho[k]+1)
else:
    nokori=k-s
    nokori%=r
    print(roop[nokori]+1)

Submission status: Accepted

Solution code:
import sys

n, k, *aaa = map(int, sys.stdin.buffer.read().split())
shortest = [-1] * n
v = 0
d = 0
while shortest[v] == -1:
    shortest[v] = d
    v = aaa[v] - 1
    d += 1
    if d == k:
        print(v + 1)
        exit()

first = shortest[v]
loop = d - first
remaining = (k - first) % loop
# print(v, first, loop, remaining + first, shortest)
ans = shortest.index(remaining + first) + 1
print(ans)

Submission status: Accepted

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

visited = dict()
a = 1
ct = 0
while a not in visited:
    visited[a] = ct
    a = A[a]
    ct += 1
    if ct == K:
        print(a)
        exit()
inv_v = {v: k for k, v in visited.items()}
print(inv_v[(K - visited[a]) % (len(visited) - visited[a]) + visited[a]])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N, K = inpl()
    A = inpl()

    nn = 1
    n = 1
    i = 0
    while True:
        nn = A[nn - 1]
        nn = A[nn - 1]
        n = A[n - 1]

        if nn == n:
            break

    roop = set()
    roop.add(n)
    root = n
    while True:
        n = A[n - 1]
        roop.add(n)
        if root == n:
            break

    n = 1
    rest = []
    while n not in roop:
        n = A[n - 1]
        rest.append(n)

    # print(roop)
    # print(rest)
    if K <= len(rest):
        print(rest[K - 1])
    else:
        for i in range((K - len(rest)) % len(roop)):
            n = A[n - 1]
        print(n)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):
    A[i]-=1
s=0
x=1
visited=[-1 for i in range(N)]
visited[0]=1
flg=0
while K:
    #print(s,K)
    a=A[s]
    x+=1
    if flg:
        K-=1
        s=a
    elif visited[a]==-1:
        K-=1

        visited[a]=x
        s=a
    else:
        #print(x,visited[s])
        K%=x-visited[a]
        flg=1
print(s+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1
path = [0]
now = 0
visited = {0}
p = 0
while True:
    if a[now] in visited:
        p = a[now]
        break
    now = a[now]
    visited.add(now)
    path += [now]
p_index = 0
for i in range(len(path)):
    if path[i] == p:
        p_index = i
        break

if k <= p_index:
    print(path[k] + 1)
else:
    print(path[p_index + (k-p_index)%len(path[p_index:])] + 1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

roop = []
flg = [0] * (N+1)
k = 1 
while True:
	roop.append(k)
	flg[k] = 1
	k = A[k-1]
	if flg[k] == 1:
		root = k
		break

i = 0
while True:
	if roop[i] == root:
		break
	i += 1

l_saisho = i
l_roop = len(roop) - i

if K < l_saisho:
	print(roop[K])
else:
	K -= l_saisho
	div, mod = divmod(K, l_roop)
	print(roop[i:][mod])

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N,K = Ints()
A = IntList()
visited = {}

Nex = [1]
now = 1
now = A[now-1]
visited[1] = 1

toS = 1

while 1:
    if not now in visited:
        if toS==K:
            print(now)
            sys.exit()
        visited[now] = 1
        now = A[now-1]
        toS += 1
    else:
        start = now
        break
    
Nex = [start]
now = start
now = A[now-1]
while now != start:
    Nex.append(now)
    now = A[now-1]    

L = len(Nex)
d = toS-L

#print(Nex)
#print(toS)
#print(toS-L)

print(Nex[(K-d)%L])

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

itta=[0]*(n+1)
now=1
cnt=1
while itta[now]==0:
    itta[now]=cnt
    now=a[now-1]
    if cnt==k:
        print(now)
        quit()
    cnt+=1

# print(itta)
# print(now)
# print(cnt)

k-=itta[now]-1
k%=cnt-itta[now]

while k>0:
    k-=1
    now=a[now-1]

print(now)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n,k=l_in()
A=l_in()

cnt=0
current = 0

memo={0: 0}

while cnt < k:
    n = A[current]-1
    cnt += 1

    if n in memo:
        delta = cnt - memo[n]

        p = (k-cnt)//delta
        cnt += p*delta
    else:
        memo[n] = cnt
    current = n
    
print(current+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
    A[i] -= 1
d = {}
n = 0
s = 0
d[0] = 0
while True:
    s = A[s]
    n += 1
    if s not in d:
        d[s] = n
    else:
        n1 = d[s]
        n2 = n
        break

if K<n1:
    s = 0
    while K>0:
        s = A[s]
        K -= 1
    ans = s+1
elif K>=n1:
    K -= n1
    K %= n2-n1
    while K>0:
        s = A[s]
        K -= 1
    ans = s+1
print(ans)

Submission status: Accepted

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

st = set()
i = 1
li = []
while i not in st:
    st.add(i)
    li.append(i)
    i = a[i]

s = i
until_s = li.index(s)

if k < until_s:
    i = 1
    for _ in range(k):
        i = a[i]

    ans = i

else:
    k -= until_s
    loop_size = len(li) - until_s
    sim_time = k % loop_size
    i = s
    for _ in range(sim_time):
        i = a[i]

    ans = i

print(ans)

Submission status: Accepted

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

x=1
while K:
    if K&1: x=A[x-1]
    K>>=1

    A2 = [None]*N
    for i,a in enumerate(A):
        A2[i]=A[A[i]-1]
    A=A2

print(x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

USE = [False] * (N + 1)

CITY = [1]
nxt = A[1]
USE[1] = True

while not USE[nxt]:
    CITY.append(nxt)
    USE[nxt] = True
    nxt = A[nxt]

loop_start = nxt
loop_start_i = CITY.index(nxt)

if K <= loop_start_i:
    print(CITY[K])
    exit()

L = len(CITY) - loop_start_i

K = (K - loop_start_i) % L
print(CITY[K + loop_start_i])

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) - 1 for a in input().split()]
    Dist = [-1] * N
    Dist[0] = 0
    now = 0
    for i in range(min(N, K)):
        nextN = A[now]
        if Dist[nextN] == -1:
            Dist[nextN] = i + 1
            now = nextN
        else:
            Left = K - i - 1
            mod = Left % (i + 1 - Dist[nextN])
            snow = nextN
            for j in range(mod):
                snow = A[snow]
            print(snow + 1)
            break
    else:
        for i, d in enumerate(Dist):
            if d == K: 
                print(i + 1)
                break
    return  0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

# from abc118_B.py

def solve(n, k, a):
    visited = [-1] * n
    tmp = [0]
    t = 0
    idx = 0
    for i in range(n):
        visited[t] = i
        nex = a[t] - 1
        if visited[nex] >= 0:
            s, e = visited[nex], i + 1
            break
        t = nex
        tmp.append(nex)
    #print(tmp, s, e, k)
    if k < len(tmp):
        ret = tmp[k] + 1
    else:
        k -= s
        k %= (e - s)
        #print(k)
        ret = tmp[s + k] + 1
    print(ret)
    return

def main():
    n, k = map(int, input().split())
    a = (list(map(int, input().split())))
    solve(n, k, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def simulate(nxt, pos, K):
    for _ in range(K):
        pos = nxt[pos]
    return pos


def main():
    N, K = [int(x) for x in input().split()]
    nxt = [int(x)-1 for x in input().split()]

    # Floyd's algorithm
    slow = 0
    fast = nxt[0]
    while fast != slow:
        fast = nxt[nxt[fast]]
        slow = nxt[slow]
    offset = 0
    slow = 0
    while fast != slow:
        fast = nxt[nxt[fast]]
        slow = nxt[slow]
        offset += 1
    loop_begin = slow
    slow = nxt[loop_begin]
    period = 1
    while slow != loop_begin:
        slow = nxt[slow]
        period += 1

    if K < offset:
        print(simulate(nxt, 0, K)+1)
    else:
        K -= offset
        K = K % period
        print(simulate(nxt, loop_begin, K)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,k = get_nums_l()
A = [-1] + get_nums_l()

# log(A)

now = A[1]
count = 1
history = {1}

while now not in history:
    # log(now, count)
    count += 1
    history.add(now)
    now = A[now]

loop_start = now
init_len = 0
now = 1
while now != loop_start:
    now = A[now]
    init_len += 1

# log("init_len", init_len)
# log("count", count)

if k <= 2*n:
    now = 1
    for i in range(k):
        now = A[now]
else:
    l = (k - init_len) % (count-init_len)

    now = loop_start
    for i in range(l):
        now = A[now]

print(now)

Submission status: Accepted

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

visited = [False]*n

p = 0
visited[0] = True

cnt = 0
while True:
    if visited[a[p]]:
        rp = a[p]
        cnt += 1
        break
    else:
        visited[a[p]] = True
        p = a[p]
        cnt += 1
    if cnt == k:
        print(p+1)
        exit()

rpcnt = 0
visited = [False]*n
p = rp
visited[p] = True
v = [p]
while True:
    if visited[a[p]]:
        rpcnt += 1
        break
    else:
        visited[a[p]] = True
        v.append(a[p])
        p = a[p]
        rpcnt += 1

first = cnt-rpcnt

print(v[(k-first)%rpcnt]+1)

Submission status: Accepted

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


journey = [1]

for i in range(2*n + 1000):
    nxt = a[journey[-1]]
    journey.append(nxt)

if k < n+1:
    print(journey[k])
    exit()

loop_end = n

loop_start = n-1

while(journey[loop_start] != journey[loop_end]):
    loop_start -= 1

period = loop_end - loop_start
k %= period


while k < n:
    k += period

print(journey[k])

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int1, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, k = nm()
m = 64
a = nl()
table = list()
table.append(a)
for _ in range(m-1):
    f = table[-1]
    g = [f[f[i]] for i in range(n)]
    table.append(g)
crt = 0
for i in range(m):
    if k & 1:
        crt = table[i][crt]
    k >>= 1
print(crt + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
g = list(map(lambda x: int(x)-1,input().split()))

check = [-1] * n
now = 0
check[now] = 0
cnt = 0
while 1:
    cnt += 1
    now = g[now]
    if check[now] != -1:
        sa = cnt - check[now]
        cnt = cnt + (k - cnt)//sa *sa
        if cnt == k:
                print(now+1)
                exit()
        while 1:
            cnt += 1
            now = g[now]
            if cnt == k:
                print(now+1)
                exit()
    else:
        check[now] = cnt
    if cnt == k:
        print(now+1)
        exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=1
v=[-1]*n
s=0
c=0
while True:
    if v[s]!=-1:
        break
    if c==k:
        print(s+1)
        exit()
    v[s]=c
    c+=1
    s=a[s]
p=c-v[s]
k-=c
k%=p
for i in range(k):
    s=a[s]
print(s+1)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x) - 1, input().split()))
    town = [[] for _ in range(n)]
    for i in range(n):
        town[i].append(a[i])
    checked = [False for _ in range(n)]
    checked[0] = True
    q = deque([0])
    loop_begin = -1
    achieve = [0]
    while q:
        now = q.pop()
        for next in town[now]:
            if not checked[next]:
                checked[next] = True
                achieve.append(next)
                q.append(next)
            else:
                loop_begin = next
    loop_idx = achieve.index(loop_begin)
    if k < loop_idx:
        print(achieve[k] + 1)
    else:
        k -= loop_idx
        achieve = achieve[loop_idx:]
        print(achieve[k % len(achieve)] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = list(map(int, input().split()))
    A = list(map(lambda x: int(x) - 1, input().split()))
    B = [-1] * N
    B[0] = K
    c = 0
    k = K
    while k:
        c = A[c]
        k -= 1
        if B[c] != -1:
            k %= (B[c] - k)
        B[c] = k
    return c + 1

print(main())

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda a: int(a) - 1, input().split()))
INF = 10**18

minDist = [INF] * N
minDist[0] = 0

now = 0
R = 0
while minDist[now] < INF:
    to = A[now]
    if minDist[to] < INF:
        R = minDist[now] + 1 - minDist[to]
        break
    minDist[to] = minDist[now] + 1
    now = to

if minDist.count(K) > 0:
    print(minDist.index(K) + 1)
    exit()

K -= minDist[now]
M = K % R
for _ in range(M):
    now = A[now]
print(now + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


#a=[int(x) for x in input().split()]
#n=int(input())

def main():
    n,k=[int(x) for x in input().split()]
    a=[int(x)-1 for x in input().split()]
    
    pr=0
    if k<n:
        for _ in range(k):
            pr=a[pr]
        print(pr+1)    
        exit(0)
    else:
        k-=n
        for _ in range(n):
            pr=a[pr]
    st=pr
    cnt,pr=1,a[st]
    while pr!=st:
        cnt+=1
        pr=a[pr]
    k%=cnt
    pr=st
    for _ in range(k):
        pr=a[pr]
    print(pr+1)
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

check = [True] * (N + 1)
count = 0

now = 1
while check[A[now]] and K:
    now = A[now]
    check[now] = False
    K -= 1

if K == 0:
    print (now)
    exit()


check = [True] * (N + 1)
count = 0

while check[A[now]] and K:
    now = A[now]
    check[now] = False
    count += 1
    K -= 1

if K == 0:
    print (now)
    exit()

K %= count

while K:
    K -= 1
    now = A[now]

print (now)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = [int(item) - 1 for item in input().split()]
visited = [0] * n

v = 0
visited[0] = 1
pre = [0]
loop = []
start = False
while True:
    v = a[v]
    if visited[v] == 1:
        start = True
    if visited[v] == 2:
        break
    if not start:
        pre.append(v)
    else:
        loop.append(v)
    visited[v] += 1 

if k < len(pre):
    print(pre[k] + 1)
    exit()
k -= len(pre)
print(loop[k % len(loop)] + 1)

Submission status: Accepted

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

s = 1
visited = [0]*(n+1)
cnt = 0
for i in range(k):
    s = al[s]
    cnt += 1
    if visited[s]>0:
        r = k - cnt
        l = cnt - visited[s]
        for _ in range(r%l):
            s = al[s]
        break
    else:
        visited[s] = cnt
print(s)

Submission status: Accepted

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

V = [-1 for _ in range(N + 1)]

s = 1

while K != 0:
    if V[s] != -1:
        step = V[s] - K
        K = K % step
        if K != 0:
            V[s] = K
            s = A[s]
            K -= 1
    else:
        V[s] = K
        s = A[s]
        K -= 1

print(s)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
double=[[0]*(n+1) for i in range(61)]
for i in range(1,n+1):
    double[0][i]=l[i-1]
for i in range(1,61):
    for j in range(n+1):
        double[i][j]=double[i-1][double[i-1][j]]
ans=1
for i in range(61):
    if k>>i&1:
        ans=double[i][ans]
print(ans)

Submission status: Accepted

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

first = [0] * (N + 1)
second = [0] * (N + 1)
roop1 = []
roop2 = []

now = 1
while True:
    if not first[now]:
        first[now] = 1
        roop1.append(now)
        now = A[now]
    elif not second[now]:
        second[now] = 1
        roop2.append(now)
        now = A[now]
    else:
        break


if K < len(roop1):
    print(roop1[K])
else:
    K -= len(roop1)
    m = K % len(roop2)
    print(roop2[m])

Submission status: Accepted

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

if a[0] == 0:
    print(1)
    exit()

rec = [0]
s = set()
s.add(0)
cur = 0
while True:
    to = a[cur]
    if to in s:
        start = rec.index(to)
        cycle = len(rec)-start
        break
    rec.append(to)
    s.add(to)
    cur = to

if start > k:
    print(rec[k]+1)
    exit()
k -= start
print(rec[start+(k%cycle)]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
cycle = []
mark = [-1]*n
pos, l = 0, 0
while 1:
    if mark[pos] >= 0:
        l = mark[pos]
        break
    mark[pos] = len(cycle)
    cycle.append(pos)
    pos = a[pos]-1
if k <= l:
    print(cycle[k]+1)
else:
    k -= l
    print(cycle[l + k%(len(cycle)-l)] + 1)

Submission status: Accepted

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

n = 1
done = [0 for i in range(N+1)]
if K > N:
    for i in range(N):
        n = A[n]
        if done[n] != 0:
            a = done[n]
            b = i + 1 - a
            break
        done[n] = i + 1

    K = (K - a) % b + a
    n = 1
for i in range(K):
    n = A[n]
print(n)

Submission status: Accepted

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

D = [0] * N
L = [0]

D[0] = 1
t = 0
c = 2
while True:
  t = A[t] - 1
  L.append(t)
  if D[t] == 0:
    D[t] = c
    c += 1
  else:
    l = D[t] - 1
    n = c - D[t]
    break
  
if l - 1 >= K:
  g = K + 1
else:
  K -= l - 1
  K %= n
  if K != 0:
    g = l + K
  else:
    g = l + n

for i in range(N):
  if D[i] == g:
    print(i + 1)
    exit()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(lambda x:int(x)-1,input().split()))
order = [-1] * N
a = 0
for i in range(K):
    if order[a] >= 0:
        r = i - order[a]
        K -= order[a]
        m = K%r
        print(order.index(order[a] + m) + 1)
        exit()
        break
    order[a] = i
    a = A[a]
else:
    print(a+1)

Submission status: Accepted

Solution code:
def main():
    INF = 1 << 30

    N, K = map(int, input().split())
    *A, = (int(x) - 1 for x in input().split())

    dist = [INF] * N
    dist[0] = 0

    cur = A[0]
    d = 1
    while dist[cur] == INF:
        dist[cur] = d
        d += 1
        cur = A[cur]

    if K <= d - 1:
        for i, x in enumerate(dist, start=1):
            if x == K:
                print(i)
                return

    if K == d:
        print(cur + 1)
        return

    K -= d
    loop_range = d - dist[cur]
    K %= loop_range
    for _ in range(K):
        cur = A[cur]
    print(cur + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

loop = [0]
s = {0}
while a[loop[-1]] not in s:
    s.add(a[loop[-1]])
    loop.append(a[loop[-1]])

idx = loop.index(a[loop[-1]])
# print(idx, loop)

if k < len(loop):
    ans = loop[k] + 1
else:
    ans = loop[(k - idx) % (len(loop) - idx) + idx] + 1
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI_()
    dist = [inf]*N

    now = 0
    flag = False
    start = 0
    for i in range(N+2):
        if(dist[now] != inf):
            cycle = i - dist[now]
            # print(cycle)
            # print(i,dist[now])
            if(K<dist[now]):
                flag = True
            else:
                K-=dist[now] ##出発点をnowにする
                start = now
                K%=cycle
            break
        dist[now] = i
        now = A[now]
    # print(K,start)
    for i in range(K):
        start = A[start]
    print(start+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc(i, k):
    for _ in range(k):
        i = A[i]
    return i

N, K = map(int, input().split())
M = 3 * 10 ** 5
A = [int(a) - 1 for a in input().split()]

if K < 10 ** 6:
    print(calc(0, K) + 1)
    exit()
i = calc(0, M)
j = A[i]
c = 1
while j != i:
    j = A[j]
    c += 1
r = c
while (K - c - M) % r:
    j = A[j]
    c += 1
print(j + 1)

Submission status: Accepted

Solution code:
import sys
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1
first = [-1] * N


if K < 2 * N:
    now = 0
    for i in range(K):
        now = A[now]
    print(now + 1)
    sys.exit()

first[0] = 0
now = 0
while True:
    next = A[now]
    if first[next] == -1:
        first[next] = first[now] + 1
        now = next
    else:
        K -= first[next]
        loop = first[now] + 1 - first[next]
        K %= loop
        now = next
        for i in range(K):
            now = A[now]
        print(now + 1)
        sys.exit()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [item-1 for item in a]

seen = [None] * n
c = 0
val = 0
seen[c] = val
val2c = {}
while True:
    val2c[val] = c
    if seen[a[c]] is not None:
        span = val - seen[a[c]] + 1
        init = seen[a[c]]
        break
    c = a[c]
    val += 1
    seen[c] = val

if k<=init:
    ans = val2c[k]
else:
    ans = val2c[(k-init)%span+init]
print(ans+1)