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())
a_l = list(map(int,input().split()))

town = 1
count = 0
town_visited = set()
while count < k:
    town_visited.add(town)
    town = a_l[town-1]
    count += 1
    if town in town_visited:
        break

k -= count
if k == 0:
    print(town)
    exit()
count = 0
town_visited = set()
while count < k:
    town_visited.add(town)
    town = a_l[town-1]
    count += 1
    if town in town_visited:
        break

remain = k%count
count = 0
while count < remain:
    town = a_l[town-1]
    count += 1
   
print(town)

Submission status: Accepted

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

d = [-1]*n
city = []
d[0] = 0
now = 0
start = 0
for i in range(n):
    city.append(now+1)
    if d[A[now]-1] != -1:
        loop = d[now] + 1 - d[A[now]-1]
        start = A[now]-1
        break
    d[A[now]-1] = d[now] + 1
    now = A[now]-1

if d[start] >= k:
    print(city[k])
else:
    print(city[d[start] + (k-d[start])%loop])

Submission status: Accepted

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

F = [False]*N
L = []
cnt = 0
ans = -1
x = 0
first = -1
while 1:
    if first==x:break
    if cnt==K:
        ans = x
        break
    if F[x]:
        if first==-1:
            first = x
        L.append(x)
    F[x]=True
    cnt += 1
    x = A[x]
if ans==-1:
    N = len(L)
    ans = L[(K-cnt)%N]
print(ans+1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    cur = 1
    visited = [-1] * (N + 1)
    visited[cur] = 0
    for i in range(1, K + 1):
        next = A[cur]
        if cur == next:
            print(next)
            return
        elif visited[next] != -1:
            mod = i - visited[next]
            start = visited[next]
            break
        else:
            visited[next] = visited[cur] + 1
            cur = next
    else:
        print(next)
        return

    K = (K - start) % mod
    print(visited.index(K + start))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dbl_max = (len(str(bin(k-1)))) -2
dbl = [[-1] * (n) for _ in range(dbl_max) ]

for j in range(n):
    dbl[0][j] = a[j] -1

for i in range(1,dbl_max):
    for j in range(n):
        dbl[i][j] = dbl[i-1][ dbl[i-1][j] ]

ans = 0
for i in range(dbl_max):
    if( (k >> i) & 1):
        ans = dbl[i][ans]

print(ans+1)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(c) for c in input().split()]
cnt = 0
p = 0
used = [False]*N
used[0] = True
while True:
  p = A[p]-1
  cnt += 1
  if used[p]:
    m = p
    break
  used[p] = True
p = 0
while m!=p and K:
  cnt -= 1
  p = A[p]-1
  K -= 1
if K==0:
  print(p+1)
  import sys
  sys.exit()
K %= cnt
while K:
  p = A[p]-1
  K -= 1
print(p+1)

Submission status: Accepted

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

    cycle = []
    visited = [False for _ in range(n)]
    now = 0

    while True:
        cycle.append(now)
        visited[now] = True
        now = a[now]-1
        if (visited[now]):
            break


    t = len(cycle)
    cstart = 0
    for i in range(t):
        if cycle[i] == now:
            cstart = i
            break

    c = t - cstart

    if k < cstart:
        print(cycle[k]+1)
    else:
        print(cycle[cstart + (k - cstart) % c]+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()))
d = [-1] * n
d[0] = 0
x = 0
while d[a[x]] == -1:
    d[a[x]] = d[x] + 1
    x = a[x]
    if k == d[x]:
        print(x + 1)
        exit(0)
x = a[x]
k -= d[x]
d1 = [-1] * n
d1[x] = 0
t = x
m = 1
while d1[a[x]] == -1:
    m += 1
    d1[a[x]] = d1[x] + 1
    x = a[x]
for i in range(n):
    if k % m == d1[i]:
        print(i + 1)

Submission status: Accepted

Solution code:
N,K,*A=map(int, open(0).read().split())
x=1
C=[None]*N
C[0]=0
c=0
while c<K:
    x=A[x-1]
    c+=1
    if C[x-1] is None:
        C[x-1]=c
    else:
        a=C[x-1]
        b=c-a
        K=(K-a)%b+a+b
        while c<K:
            x=A[x-1]
            c+=1
        break
print(x)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def print_ans(B):
    for b in B:
        b.sort(key=lambda l: int(l))
        print(" ".join(b))



def main():
    N, K = read_values()
    A = list(read_index())

    P = [-1] * N

    k = 0
    n = 0
    while P[n] == -1: 
        P[n] = k
        n = A[n]
        k += 1

    if k > K:
        print(P.index(K) + 1)
        return

    a = (K - P[n]) % (k - P[n]) + P[n]
    print(P.index(a) + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))

dbl = [[0] * 61 for _ in range(N)]
for i in range(N): dbl[i][0] = a[i] - 1

for k in range(60):
  for i in range(N):
    x = dbl[i][k]
    dbl[i][k + 1] = dbl[x][k]

x = 0
while K:
  x = dbl[x][K.bit_length() - 1]
  K -= 1 << (K.bit_length() - 1)
print(x + 1)

Submission status: Accepted

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

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

Seq = [-1]*(N+1)
Seq[1] = 0
now = 1
while True:
    n = A[now]
    if Seq[n] == -1:
        Seq[n] = Seq[now] + 1
        now = n
    else:
        cycle = Seq[now] + 1 - Seq[n]
        now = n
        break

if Seq[now] > K:
    for n in range(N+1):
        if Seq[n] == K:
            print(n)
            break
else:
    rem = (K-Seq[now])%cycle
    for _ in range(rem):
        now = A[now]
    print(now)

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

e = [True] * N
q = []
now = 0

while e[now]:

    e[now] = False
    q.append(now)

    now = A[now]


q1 = []
q2 = []

fl = True
for i in q:
    if now == i:
        fl = False
        
    if fl:
        q1.append(i)
    else:
        q2.append(i)
        
if K < len(q1):

    print ( 1 + q1[K])

else:
    K -= len(q1)
    print ( 1 + q2[K % len(q2)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
x, cnt = 0, 0
vis = [-1]*N
if K > N:
    while 1:
        vis[x] = cnt
        cnt += 1
        x = A[x]-1
        if vis[x] != -1:
            break
    for i in range((K-vis[x])%(cnt-vis[x])):
        x = A[x]-1
else:
    for i in range(K):
        x = A[x]-1
print(x+1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    v = set()

    c = 1
    cnt = 0
    while True:
        if c in v:
            break
        v.add(c)
        cnt += 1
        c = A[c - 1]
        if cnt == K:
            print(c)
            return
    K -= cnt

    syuki = []
    syuki.append(c)
    c = A[c - 1]
    while True:
        if c == syuki[0]:
            break
        syuki.append(c)
        c = A[c - 1]
    print(syuki[K % len(syuki)])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def solve(N,K,A):
    visited = [None]*N
    cur = 0
    for i in range(K):
        if visited[cur] is None:
            visited[cur] = i
            cur = A[cur]-1
        else:
            break
    else:
        print(cur+1)
        return

    K -= i
    K %= i-visited[cur]

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

    print(cur+1)


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

solve(N,K,A)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [a - 1 for a in A]
    visited = {0}
    loop = [0]
    now = 0
    while A[now] not in visited:
        now = A[now]
        visited.add(now)
        loop.append(now)
    
    for i,s in enumerate(loop):
        if s == A[now]:
            X = loop[:i]
            loop = loop[i:]
            break
    if K < len(X):
        print(X[K] + 1)
    else:
        K -= len(X)
        K %= len(loop)
        print(loop[K] + 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

cnt = 0
now = 0

visited = [0]*N
while not visited[now]:
	visited[now] = cnt
	cnt += 1
	now = A[now]-1
	if cnt == K:
		print(now+1)
		exit()

K -= visited[now]
K = K%(cnt-visited[now])
visited = [0]*N
for i in range(K):
	now = A[now]-1
print(now+1)

Submission status: Accepted

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

st = set()
st.add(0)

oof = [1]

cur = a[0] - 1

while cur not in st:
    st.add(cur)
    oof += [cur+1]
    cur = a[cur] - 1
ind = oof.index(cur+1)
#print(oof,ind)

if k <= ind:
    print(oof[k])
else:
    print(oof[ind + (k-ind) % (len(oof) - ind)])

Submission status: Accepted

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

cur = 0
count = 0
v_set = set()
v_list = []

while cur not in v_set:
    v_set.add(cur)
    v_list.append(cur)

    cur = a[cur] - 1
    count += 1

l_start = v_list.index(cur)
l_end = len(v_list)

if k < l_start:
    print(v_list[k] + 1)
else:
    print(v_list[l_start + (k - l_start) % (l_end - l_start)] + 1)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    LV = K.bit_length()
    nxt = [[0] * (LV+1) for _ in range(N+1)]
    for i in range(N):
        nxt[i+1][0] = A[i]
    for lv in range(1, LV+1):
        for i in range(1, N+1):
            nxt[i][lv] = nxt[nxt[i][lv-1]][lv-1]

    i = 1
    for j in range(LV+1):
        if K >> j & 1:
            i = nxt[i][j]
    print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
cities = [0]
c = 0
used = [False] * N
used[0] = True
while not used[A[c]]:
    used[A[c]] = True
    cities.append(A[c])
    c = A[c]
x = cities.index(A[c])
if K < x:
    print(cities[K] + 1)
else:
    K -= x
    K %= len(cities) - x
    print(cities[x + K] + 1)

Submission status: Accepted

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


g = [aa - 1 for aa in a]

root = []
seen = set()

cur = 0
while True:
    seen.add(cur)
    root.append(cur)

    cur = g[cur]
    if cur in seen:
        break

for i in range(len(root)):
    if root[i] == cur:
        break

p = i
n_loop = len(root) - p

if k <= p:
    print(root[k] + 1)
else:
    idx = ((k - p) % n_loop + p) % len(root)
    print(root[idx] + 1)

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

# Destination
t = [[-1] * N for _ in range(61)]
t[0] = [v - 1 for v in A]
for k in range(60):
    for i in range(N):
        t[k + 1][i] = t[k][t[k][i]]

u = 0
for k in range(61):
    if K >> k & 1:
        u = t[k][u]
        
print(u + 1)

Submission status: Accepted

Solution code:
#problems3
n,s=map(int,input().split())
a=1
lists=list(map(int,input().split()))
visited=[False for i in range(n+1)]
data=[]
now=a
flag=True
while flag:
    now=lists[now-1]
    if visited[now]==False:
        visited[now]=True
        data.append(now)
    else:
        data.append(now)
        flag=False


#data=[...(loop)...]
looping=0
for i in range(len(data)):
    if data[i]==data[-1]:
        mod=i
        index=i
        looping=data[i:-1]
        loop=len(data)-1-index
        break

U=(s-mod)%loop
if s<=mod:
    print(data[s-1])
elif s>mod:
    print(looping[U-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
now = 1
used = [-228] * (n + 191)
used[1] = -1
cn = -292
ahah = 1
for _ in range(k):
    now = A[now]
    if used[now] != -228:
        cn = _ + 1 - used[now] - 1
        break
    used[now] = _
    ahah += 1
if cn == -292:
    print(now)
    exit(0)
for i in range((k - ahah) % cn):
    now = A[now]
print(now)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    #print(locat_doubling)
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

if k <= n:
    i = 0
    for _ in range(k):
        i = a[i]
    print(i + 1)
    exit()

visit = [False] * n
visit[0] = True
lon = [0] * n

i = 0
l = 0
while True:
    i = a[i]
    l += 1
    if visit[i]:
        break
    visit[i] = True
    lon[i] = l

kk = (k - lon[i]) % (l - lon[i])
for _ in range(kk):
    i = a[i]
print(i+1)

Submission status: Accepted

Solution code:

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

a = [[0]+list(map(int, input().split()))]
for k in range(62):
    a.append([a[k][a[k][i]] for i in range(n+1)])

res = 1
for k in list(range(62))[::-1]:
    if m >= 2**k:
        res = a[k][res]
        m -= 2**k
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = [[0, *(int(x) for x in input().split())] if p == 0 else [0 for i in range(n + 1)] for p in range(60)]
for p in range(1, 60):
    for i in range(1, n + 1):
        a[p][i] = a[p - 1][a[p - 1][i]]
ans = 1
for p in range(60):
    if k & (1 << p):
        ans = a[p][ans]
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = tuple(map(lambda n: int(n) - 1, input().split()))
visited = [0] * N
next_town = 0
order = []
while True:
    if visited[next_town]:
        break
    order.append(next_town)
    visited[next_town] = 1
    next_town = A[next_town]
first_loop = len(order)
offset = order.index(next_town)
second_loop = first_loop - offset
if K < first_loop:
    print(order[K] + 1)
else:
    print(order[offset + (K - first_loop) % second_loop] + 1)

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def calc_path_loop(L):
        appeared = dict()
        cnt = 0
        current = 0
        while True:
            if current not in appeared:
                appeared[current] = cnt
            else:
                return appeared[current], cnt - appeared[current],
            cnt += 1
            current = L[current]

    n, k = mi()
    L = lmi_0()
    a, b = calc_path_loop(L)
    # print(f"{a} {b}")
    simu_times = k if a >= k else a + (k - a) % b
    current = 0
    for _ in range(simu_times):
        current = L[current]
    print(current + 1)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

B = [0]
F = [-1] * n
F[0] = 0
s = A[0]
i = 0
while F[s] == -1:
    i += 1
    B.append(s)
    F[s] = i
    s = A[s]

# print(F[s], i+1)

if k <= F[s]:
    print(B[k] + 1)
else:
    ind = (k-F[s]) % (i+1-F[s]) + F[s]
    print(B[ind] + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ls = [a[:]]
for i in range(70):
  lsa = [0]*n
  for j in range(n):
    lsa[j] = ls[-1][ls[-1][j]-1]
  ls.append(lsa)
ans = 1
for i in range(71)[::-1]:
  if k&1<<i:
    ans = ls[i][ans-1]
print(ans)

Submission status: Accepted

Solution code:
import os

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

A = np.array(A, dtype=int) - 1

dp = np.zeros((K.bit_length() + 1, N), dtype=int)
dp[0, :] = A
for h in range(1, len(dp)):
    dp[h] = dp[h - 1][dp[h - 1]]

ans = 0
for i in reversed(range(K.bit_length())):
    if K >> i & 1:
        ans = dp[i][ans]
print(ans + 1)

Submission status: Accepted

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

doubling=[[0 for i in range(N)] for i in range(0,70)]
for i in range(N):
    doubling[0][i]=A[i]

for i in range(1,70):
    for j in range(N):
        doubling[i][j]=doubling[i-1][doubling[i-1][j]]

ans=0
for i in range(0,70):
    if K>>i &1==1:
        ans=doubling[i][ans]

print(ans+1)

Submission status: Accepted

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

visit = [0] * n
visit[0] = 1
keiro = [1]

s = 1
now = 1

while True:
    x = a[now - 1]
    if visit[x - 1] == 1:
        break
    now = x
    visit[x - 1] = 1
    keiro.append(x)

l1 = len(keiro)
l2 = keiro.index(x)

if k < l1:
    print(keiro[k])
else:
    p = (k - l2) % (l1 - l2)
    print(keiro[l2 + p])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
log_size = 100
dp = [[0]*N for _ in range(log_size)]

for i in range(N):
    dp[0][i] = A[i]-1
    
for i in range(1, log_size):
    for j in range(N):
        dp[i][j] = dp[i-1][dp[i-1][j]]

c = 0
cur = 0
    
while K>0:
    if K&1:
        cur = dp[c][cur]
        
    c += 1
    K >>= 1

print(cur+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda c: int(c)-1, input().split()))
V = [-1] * N
i = 0
l = 0
while True:
	if V[i] != -1: break
	V[i] = l
	i = A[i]
	l += 1
	if l == K:
		print(i + 1)
		raise SystemExit
cyc = l - V[i]
K -= V[i]
K %= cyc
for _ in range(K):
	i = A[i]
print(i + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    A = list(map(lambda x:int(x) - 1, input().split()))

    nexts = []
    nexts.append(A)
    for _ in range(61):
        next = nexts[-1]
        nnext = [None] * n
        for i in range(n):
            nnext[i] = next[next[i]]
        nexts.append(nnext)

    now = 0
    for d in range(61):
        if (k >> d) & 1:
            now = nexts[d][now]

    print(now + 1)
resolve()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17

def main():
    n, k = getList()
    nums = [0] + getList()
    cnt = 1
    if k == 1:
        print(1)
        return
    cur = 1
    visited = [-1 for i in range(n+1)]
    visited[1] = 1
    rooped = False
    while(True):
        cur = nums[cur]
        cnt += 1

        if visited[cur] != -1:
            roop = cnt - visited[cur]
            k -= ((k-cnt) // roop) * roop
            rooped = True
        if not rooped:
            visited[cur] = cnt


        if cnt == k:
            print(nums[cur])
            return

        # print(k, cnt, cur)
        # print(visited)
        # if cnt >= 10:
        #     break

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def ZZ(): return list(map(int, input().split()))
def Z(): return int(input())

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

def mul(a, b):
    return [a[b[i]] for i in range(len(a))]

def beki(a, b):
    res = list(range(len(a)))
    while b > 0:
        if b & 1:
            res = mul(res, a)
        a = mul(a, a)
        b >>= 1
    return res

A = beki(A, K)
print(A[0] + 1)

Submission status: Runtime Error

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

visited = set([1])
cnt = 0
t = [1]
p = 1

while AS[p-1] not in visited and cnt < K:
  a = AS[p-1]
  visited.add(a)
  t.append(a)
  p = a
  cnt += 1

if cnt == K:
  print(t[-1])

f_cnt = t.index(AS[p-1])
loop_cnt = cnt + 1 - f_cnt
print(t[f_cnt+(K-f_cnt)%loop_cnt])

Submission status: Runtime Error

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,k=input2()
A=input_array()

# ある地点から循環に陥る
judge=[True]*n
tmps=[1] #循環手前
count=0 #参照地点

for i in range(2*(10**5)+1):
	if judge[count]==True:
		judge[count]=False
		count=A[count]-1
		tmps.append(count+1)
	else:
		break

loop_st=tmps[-1]
loops=tmps[loop_st:-1]


if k<loop_st:
	print(tmps[k])
else:
	k=k-loop_st
	k%=len(loops)
	print(loops[k])

Submission status: Runtime Error

Solution code:
n,k=input2()
A=input_array()

# ある地点から循環に陥る
tmps=[1] #循環手前
loops=[] #循環
st=0 #循環が始まる地点
count=0 #参照地点

for i in range(10**5):
	if A[count] not in tmps:
		tmps.append(A[count])
	elif (A[count] in tmps) and (A[count] not in loops):
		loops.append(A[count])
		st=i
	else:
		break
	count=A[count]-1


if k<=st:
	print(tmps[k-1])
else:
	ans=(k-(st-1))%len(loops)
	print(loops[ans])

Submission status: Runtime Error

Solution code:

url = "https://atcoder.jp/contests/abc162/tasks/abc162_d"
import itertools


def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    route = []
    istuka = [0] * (n+1)
    next = 1
    # 同じ街に訪れるまでループ
    for _ in range(k):
        if istuka[next] == 1:
            break
        else:
            istuka[next] = 1
            route.append(next)
        next = a[next - 1]
    ans = route[route.index(next):]
    idx = (k - route.index(next)) % len(ans)
    print(ans[idx])



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

path = [0]*N

pos = 1
for i in range(K):
    if pos in path: break
    path[i] = pos
    pos = A[pos]

head = path[:path.index(pos)]
rep = path[path.index(pos):i]

print(rep[(K - len(head)) % len(rep)])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
data=[0]*(n+1)
data[1]=1
ans=[1]
res=0
for i in range(n):
  p=a[res]
  if data[p]==0:
    data[p]=1
    ans.append(p)
    res=p-1
  else:
    res=ans.index(p)
    break
if len(ans)>=k:
  print(ans[k])
else:
  m=len(ans)-res
  k-=res
  d=k%m
  print(ans[res+d])

Submission status: Runtime Error

Solution code:

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

memo = [1]
setm = set(memo)
cnt = 1
to = 1
while cnt <= k:
    to = a[to-1]
    if to not in setm:
        memo.append(to)
        setm.add(to)
        cnt += 1
    else:
        break
        
idx = memo.index(to)
kidx = ((k - len(memo))%(len(memo)-idx))
if cnt<=k:
    print(memo[-2])
else:
    print(memo[-1] if kidx==0 else memo[idx:][kidx-1])