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  = [0]
A += list(map(int,input().split()))
B = [-1 for _ in range(n+1)]
B[1] = 0
now =1
cnt = 0
cic = 0
for i in range(1,n+1):
    now = A[now]
    cnt +=1
    if B[now] ==-1:
        B[now] = cnt
    else:
        cic = cnt - B[now]
        road = B[now] 
        break

if k <= road:
    print(B.index(k)) 
else:
    print(B.index(((k-road)%cic+road)))

Submission status: Accepted

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

i2p = {0:1}
p2i = {1:0}
cur = A[0]
is_loop = {}
for i in range(N+1):
    is_loop[i] = False
i = 1
while True:
    i2p[i] = cur
    p2i[cur] = i
    is_loop[cur] = True
    if is_loop[A[cur-1]]:
        break
    cur = A[cur-1]
    i+=1
i = p2i[A[cur-1]]
num_loop = len(i2p) - i 
if K < i:
    print(i2p[K])
else:
    print(i2p[i+(K-i)%num_loop])

Submission status: Accepted

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

import sys


INF = sys.maxsize // 10


def determine_dest(n, k, bs):
    source = 0
    path_from_source = [0]
    dist_from_source = [INF] * n
    dist_from_source[source] = 0
    cur = source
    start_cycle_vertex = None
    len_cycle = None
    dist_to_cycle = None
    for _ in range(n + 1):
        ne = bs[cur]
        # print(cur, ne, file=sys.stderr)
        if dist_from_source[ne] >= INF:
            dist_from_source[ne] = dist_from_source[cur] + 1
            path_from_source.append(ne)
            cur = ne
        else:
            # cycle detected
            start_cycle_vertex = ne
            dist_to_cycle = dist_from_source[ne]
            len_cycle = dist_from_source[cur] - dist_to_cycle + 1
            break
    if k < dist_to_cycle:
        return path_from_source[k]
    else:
        rest_k = k - dist_to_cycle
        rem = rest_k % len_cycle
        return path_from_source[dist_to_cycle + rem]
        


def main():
    n, k = (int(z) for z in input().split())
    bs = [int(b) - 1 for b in input().split()]
    res = determine_dest(n, k, bs) + 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
c = [[0]*n for i in range(3)]
c[0][0] = 1
town = 0
count = 0
while count <= n:
    count += 1
    town = a[town] -1
    c[0][town] += 1
    if c[0][town] == 2:
        c[2][town] = count
        roop_0 = town
        break
    else:
        c[1][town] = count
        
loop_size = c[2][roop_0] - c[1][roop_0]

if k < c[1][roop_0]:
    print(c[1].index(k)+1)
else:
    ans = c[1][roop_0]+((k-c[1][roop_0])%loop_size)
    print(c[1].index(ans)+1)

Submission status: Accepted

Solution code:
# N, K = 4, 5
# ARR = [3, 2, 4, 1]

# N, K = 6, 727202214173249351
# ARR = [6, 5, 2, 5, 3, 2]

import sys
sys.setrecursionlimit(100000000)

N,K = map(int,input().split())
ARR = list(map(int,input().split()))
NodeStatus = [False] * N
NodeFirstSteps = [0] * N
L = 0
STARTLINDEX = 0
OrderARR = []


def dfs(pos, arr, step):
    if NodeStatus[pos] == True:
        L = (step - NodeFirstSteps[pos])
        STARTLINDEX = NodeFirstSteps[pos]
        print(OrderARR[(K - STARTLINDEX) % L + STARTLINDEX] + 1)
        return

    if step == K:
        print(pos+1)
        return

    OrderARR.append(pos)
    NodeStatus[pos] = True
    NodeFirstSteps[pos] = step
    dfs(arr[pos] - 1, arr, step + 1)


dfs(0, ARR, 0)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
A = [0] + [int(i) for i in input().split()]
B = [1]
s = set()
s.add(1)
while(True):
    tmp = A[B[-1]]
    if not tmp in s:
        B.append(tmp)
        s.add(tmp)
    else:
        head = B.index(tmp)
        break
if K >= len(B[:head]):
    K = (K - len(B[:head]))  % len(B[head:])
    print(B[head:][K])
else:
    print(B[K])

Submission status: Accepted

Solution code:
n,k=list(map(int, input().split()))
a=list(map(int, input().split()))
b=[0]*(n+1)
for i in range (n):
    b[i+1]=a[i]
ctr=[-1]*(n+1)
ctr[1]=0
x=1
c=0
s=0
while c==0:
    y=b[x]
    s+=1
    if ctr[y]==-1 and y!=1:
        ctr[y]=s
        x=y
    else:
        ll=s-ctr[y]
        c+=1
        f=ctr[y]

if k<f:
    ans=ctr.index(k)
else:
    zz=(k-f)%ll
    ans=ctr.index(zz+f)
print(ans)

Submission status: Accepted

Solution code:
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
d={}
town=1
telep=0
ls=0
lc=0
d[town]=0
for i in range(n):
    telep=l[town-1]
    town=telep
    if(ls==0):
        lc+=1
    if(town not in d):
        d[town]=lc
    elif(ls==0):
        ls=town
lc=d[ls]
if(k<=lc):
    town=1
    telep=0
    for i in range(k):
        telep=l[town-1]
        town=telep
    print(town)
else:
    k-=lc
    town=ls
    telep=0
    k=k%(max(d.values())-lc+1)
    for i in range(k):
        telep=l[town-1]
        town=telep
    print(town)

Submission status: Accepted

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

to = [0]
to += list(map(int, input().split()))

passed = [0] * (n + 1)

circle = [1]
st = -1
while True:
  nx = to[circle[-1]]
  if passed[nx] == 1:
    st = nx
    break
  circle.append(nx)
  passed[nx] = 1
  

l1 = circle.index(st)
l2 = len(circle) - l1

if k < l1:
  print(circle[k])
elif k < l1 + l2:
  print(circle[k])
else:
  div = (k - l1) % l2
  print(circle[l1+div])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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


visited = set()
visited.add(1)
lst = [1, ]

now = 1
flg = 0
for i in range(K):
    now = A[now-1]
    if now in visited:
        last = K - i
        loop_point = now
        flg = 1
        break
    visited.add(now)
    lst.append(now)
if not flg:
    print(lst[-1])
    exit()    

for i in range(len(lst)):
    if lst[i] == loop_point:
        inter = i
        loop = lst[i:]

last = (last-1) % len(loop)
print(loop[last])

Submission status: Accepted

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

loop = 0
use = [0] * n
now = 0
use[now] = 1
x = [1]
for _ in range(n):
   next = a[now] - 1
   x.append(next+1)
   if use[next] == 0:
      use[next] = 1
      now = next
   else:
      break
loop = x.pop(-1)

tmp = x.index(loop)
y = x[:tmp]
x = x[tmp:]
#print(y, x)

if k < len(y):
   kk = k % len(y)
   print(y[kk])
else:
   k -= len(y)
   kk = k % len(x)
   print(x[kk])

Submission status: Accepted

Solution code:
#int(input())
#int(x) for x in input().split()
#map(int,input().split())
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
co=0
s=set([1])
i=0
path=[1]
j=0
while True:
	co+=1
	path.append(a[i])
	if a[i] in s:
		j=path.index(a[i])
		break
	else:
		s.add(a[i])
	i=a[i]-1
#print(path)
if k<=j:
	print(path[k])
else:
	k-=j
	path=path[j+1:]
	k-=1
	k=k%(len(path))
	print(path[k])

Submission status: Accepted

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

A0=list(range(N))

def calc_zero(n):
    return n * 0

A0 = list(map(calc_zero, A0))

temp=0
tempv=[]

for i in range(K):
  if A0[temp]>=1:
    loop=i-A0[temp]
    t=(K-A0[temp])%loop
    temp=tempv[A0[temp]+t-1]
    break
  else:
    A0[temp]=i
    temp=A[temp]-1
    tempv.append(temp)

print(temp+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:50:56 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

city = [False for i in range(N)]
city[1-1] =True
now = 1

counta1 = 0
while True:
    counta1 += 1
    prev = now
    now = A[now-1]
#    print(prev,now,counta1)
    if city[now-1]:
        break
    elif counta1 == K:
        print(now)
        sys.exit()
    else:
        city[now-1] = True

counta = 1
rout = []
rout.append(now)
while now != prev:
    now = A[now-1]
    rout.append(now)
    counta +=1
#    print(now,rout,counta)

ans = rout[(K-counta1) % counta]
print(ans)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
d2 = {}
d3 = {}
loopc = 0
for i in range(1, n + 1):
    d[i] = a[i - 1]


b = d[1]
d2[b] = 1
d3[i] = b
amari = 0
if k >= 2:
    if n >= k:
        for i in range(2, k + 1):
            if b in d:
                b = d[b]
        print(b)
    else:
        for i in range(2, n + 1):
            if b in d:
                b = d[b]
                if b not in d2:
                    d2[b] = i
                    d3[i] = b
                elif b in d2:
                    loopc = i - d2[b]
            else:
                print(b)
                sys.exit()

        amari = k - n
        amari = amari % loopc
        for i in range(amari):
            b = d[b]
        print(b)
else:
    print(b)

Submission status: Accepted

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

ind =1
dind = a[ind-1]
aset = set([1,])
arr = [1,]

while dind not in aset:
    ind = dind
    dind = a[ind-1]
    arr.append(ind)
    aset.add(ind)


# print(arr, dind)
ui = arr.index(dind)
offset = ui+1
unit = arr[ui:]
# print(unit,offset)
if k<offset:
    print(arr[k])
else:
    k-=offset
    k=k%len(unit)
    if k==len(unit)-1:
        k=0
    else:
        k+=1
    print(unit[k])

Submission status: Accepted

Solution code:
###
# main
if(__name__ == '__main__'):
    # input
    n, k = map(int, input().split(" "))
    a = list(map(int, input().split(" ")))

    pos_li = []
    tele_dic = {}
    current = 0
    ans = 0
    for i in range(k):
        if current in tele_dic:
            # detect loop
            cycle = i - tele_dic[current]
            mod = (k - tele_dic[current]) % cycle
            ans = pos_li[tele_dic[current]+mod]
            break
        else:
            pos_li.append(current)
            tele_dic[current] = i
            current = a[current]-1
    else:
        ans = current

    # output
    print(ans+1)
# else:
    # do nothing

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
s = set()
loop = []
ls = set()
pas1 = []
pas2 = []
now = 1
count = 0
if k == 1:
    print(l[0])
    exit()
for i in range(2*n):
    a = l[now-1]
    if a in s:
        if a in ls:
            k -= count+1
            print(loop[k%len(loop)])
            
            exit()
        else:
            ls.add(a)
            loop.append(a)
            now = a
            count += 1
            if count == k:
                print(a)
                exit()
        
        
    else:
        now = a
        s.add(a)
        count += 1
        pas1.append(a)
        
        if count == k:
            print(a)
            exit()

Submission status: Accepted

Solution code:
N , K = map(int, input().split())
li = list(map(int, input().split()))
if K < N:
    town = 0
    for i in range(K):
        town = li[town]-1
    print(town+1)
else:
    li2 = [0for i in range(N)]
    count = 1
    town = 0
    while(1):
        if li2[town] != 0:
            num = count - li2[town]
            num2 = li2[town]
            break
        li2[town] = count
        town = li[town]-1
        count += 1

    K = K - (num2 - 1)
    mod = K % num
    #print(mod)
    #print(li2, num, num2)
    for i in range(mod):
        town = li[town] -1
    print(town+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = [int(x) for x in input().split()]
appeared = [False] * (n + 1)
load = [1]
cnt = 0
cycle_init = -1
no_cycle = False
while True:
    nxt = A[load[-1] - 1]
    if appeared[nxt]:
        cycle_init = nxt
        break
    else:
        load.append(nxt)
        appeared[nxt] = True
    cnt += 1
    if cnt == n:
        no_cycle = True
        break
if no_cycle:
    print(load[k])
else:
    idx_ci = load.index(cycle_init)
    cycle = load[idx_ci:]
    b_cycle = load[:idx_ci]
    lenb = len(b_cycle)
    if k < lenb:
        print(b_cycle[k])
    else:
        m = len(cycle)
        k = k - lenb
        print(cycle[k % m])

Submission status: Accepted

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

X = 0
V[0] = 0
T = 0

while T < K:
  T += 1
  X = A[X]-1
  if V[X] != -1:
    t = T - V[X]
    k = (K - T) % t
    for i in range(k):
      X = A[X]-1
    break
  V[X] = T

print(X+1)

Submission status: Accepted

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

li = [-10]*(n)
tmp = ai[0]

st = -1

for i in range(n+1):
    #tmp = ai[i]
    if li[tmp-1] != -10:
        prd = i - li[tmp-1]
        st = li[tmp-1]+1
        break
    li[tmp-1] = i
    tmp = ai[tmp-1]
    #print(tmp)
    
#print(li,prd,tmp)
pat = 0
if ai[tmp-1] == tmp:
    pat = 1

#print(prd,li,st,pat)
#exit()

#if pat == 1:
#    print(tmp)
#    exit()
if k <= st:
    for i in range(n):
        if li[i] == k-1:
            print(i+1)
            exit()
else:
    idx = (k-st) % prd
    #print(idx,idx,idx)
    for i in range(n):
        if li[i] == st-1+idx:
            print(i+1)
            exit()

Submission status: Accepted

Solution code:
# D - Teleporter

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

done = set()
path = []
now = 0
while True:
    if now in done:
        break
    else:
        path.append(now)
        done.add(now)
        now = A[now] - 1

start = path.index(now)
loop = len(path) - start
if K < start:
    steps = K
else:
    steps = (K - start)%loop + start

#print(start, loop, steps, path)
print(path[steps]+1)

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
v = [0 for i in range(n+1)]
v[0] = 1
r = [1]
p = a[0]
while v[p]==0:
  v[p] = 1
  r.append(p)
  if len(r)==k+1:
    break
  p = a[p-1]
if len(r)==k+1:
  print(p)
else:
  idx = r.index(p)
  k -= idx
  print(r[k%(len(r)-idx)+idx])

Submission status: Accepted

Solution code:
def search(now, teleporter, limit):
    visit = [-1] * len(teleporter)
    cnt = 0
    
    while visit[now] == -1:
        if limit <= cnt:
            break
        
        visit[now] = cnt
        cnt += 1
        now = teleporter[now]
        
    
    return now, cnt, cnt - visit[now]
    

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

start, initial_cnt, repeat_num = search(0, a, 10**6)

#print(start, initial_cnt, repeat_num)

if k < initial_cnt:
    start = 0
    r = k
else:
    r = (k - initial_cnt) % repeat_num

#print(r)

ans, _, _ = search(start, a, r)

print(ans + 1)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(j) for j in input().split()]
dp = [0] * (n + 1)
start = 0
period = 0
for i in range(1, n + 1):
    dp[i] = a[dp[i - 1]] - 1
b = dp[n]
if k < n:
    print(dp[k] + 1)
else:
    for j in range(n - 1, -1, -1):
        if dp[j] == b:
            period = n - j
            break
    for i in range(n + 1 - period):
        if dp[i] == dp[i + period]:
            start = i
            break
    k = start + (k - start) % period
    print(dp[k] + 1)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()
    a = [ai - 1 for ai in a]

    junkan_point = 0
    visited = [0, a[0]]
    next = a[0]

    visited_set = set(visited)

    for _ in range(n+5):
        if a[next] in visited_set:
            junkan_point = a[next]
            break
        else:
            visited.append(a[next])
            visited_set.add(a[next])
            next = a[next]

    tmp_idx = visited.index(junkan_point)
    junkan_visited = visited[tmp_idx:]

    tmp = len(visited) - len(junkan_visited)
    if k < tmp:
        print(visited[k]+1)
    else:
        idx = (k - tmp) % len(junkan_visited)
        print(junkan_visited[idx] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
city_num, like_num = map(int, input().split())
arrival = list(map(int, input().split()))
for _ in range(city_num):
    arrival[_] -= 1

am = 0
a2m = 0
l_lis = [0, arrival[0]]  # l_lis[0]は0回

am = arrival[am]
a2m = arrival[arrival[a2m]]

while(am != a2m):
    am = arrival[am]
    a2m = arrival[arrival[a2m]]
    l_lis.append(am)

# city_lが循環開始
l = 0
x = am
y = 0
while(x != y):
    x = arrival[x]
    y = arrival[y]
    l += 1
# print(l)


r = 1
am = x
a2m = x
r_lis = []  # r_lis[0]は循環開始の次
am = arrival[am]
a2m = arrival[arrival[a2m]]
while(am != a2m):
    r_lis.append(am)
    am = arrival[am]
    a2m = arrival[arrival[a2m]]
    r += 1
    # print(am+1, a2m+1, r)

# print(r)

times = 0
if(l > like_num):
    times = like_num
else:
    times = l + (like_num - l) % r
ans = 0
for _ in range(times):
    ans = arrival[ans]

print(ans+1)

Submission status: Accepted

Solution code:




data = input().split()

N, k = int(data[0]), int(data[1])

tab = []

data = input().split()
for i in range(N):
    tab.append(int(data[i]) - 1)


parcour = []
tmp = [0] * N

position = 0

while (tmp[position] == 0):
    parcour.append(position)
    tmp[position] = 1
    position = tab[position]
i = 0
while parcour[i] != position:
    i+= 1

sizeCycle = len(parcour) - i 

#print (parcour)
if (k < len(parcour)):
    print(parcour[k] + 1)
else:
    print(parcour[i + ((k - i) % sizeCycle)] + 1)

Submission status: Accepted

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

i = 0
lp = 0
step = []
while visited[i] == 0:
  visited[i] = 1
  step.append(i)
  next_visit = A[i] 
  lp += 1
  if lp == k:
    print(next_visit + 1)
    exit()
  i = next_visit

lp_start = step.index(i)
syuki = lp - lp_start

if lp_start > k:
  ans = step[k]
else:
  cnt = (k - lp_start) % syuki
  ans = step[lp_start:][cnt] + 1

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
check=[0]*(N)
check[0]=1
D=[]
C=[0]
p=0
for i in range(N):
  pp=A[p]-1
  if check[pp]==0:
    check[pp]=1
    C.append(pp)
    p=pp
  else:
    roop=pp
    break
rs=C.index(roop)
if K<=rs-1:
  print(C[K]+1)
else:
  K-=(rs-1)
  F=C[rs:]
  e=K%(len(F))
  print(F[e-1]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
tele=[0 for _ in range(n+1)]
cnt=1
v=1
while True:
    if tele[v]!=0:
        break
    else:
        tele[v]=cnt
        cnt+=1
        v=A[v-1]

circle_in=tele[v]
circle=[]
for idx,t in enumerate(tele):
    if t<circle_in:
        continue
    else:
        circle.append((t,idx))
circle.sort()

circle_len=len(circle)
if circle[0][1]==1:
    circle_idx=k%(circle_len)
    ans=circle[circle_idx][1]

elif k<circle_in:
    ans=tele.index(k+1)

else:
    k=k-(circle_in-1)
    circle_idx=k%(circle_len)
    ans=circle[circle_idx][1]

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
# k = int(input())
a = 1
B = [b-1 for b in map(int,input().split())]
d = [-1]*n
d[a-1] = 0
now = a-1
while True:
    if d[B[now]] == -1:
        d[B[now]] = d[now] + 1
        now = B[now]
    else:
        loop = d[now] - d[B[now]] + 1
        start = d[B[now]]
        break
print(d.index((k-start)%loop + start) + 1 if start < k else d.index(k) + 1)

Submission status: Accepted

Solution code:
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7


n, k = multi_int_input()

a = list_input()


prev = 1

if k < n:
    
    for i in range(k):
        nextTown = a[prev-1]
        prev = nextTown

    print(prev)

else:

    seti = {}
    seti[1] = 0
    count = 0
    cycle = 0
    x = 0
    order = [1]
    while(True):
        count+=1
        nextTown = a[prev-1]
        order.append(nextTown)
        prev = nextTown
        if nextTown in seti:
            cycle = count - seti[nextTown]
            x = seti[nextTown]
            break
        else:
            seti[nextTown] = count

    # print(k, cycle, x, seti)
    k = k - (x - seti[1])
    # print(k, order)
    print(order[x+(k%cycle)])

Submission status: Accepted

Solution code:
N,K = map(int,input().split(" "))
A = [int(i)-1 for i in input().split(" ")]
check = [0]*N
here = 0
for _ in range(2*N):
    check[here] += 1
    here = A[here]
c = sum([1 for i in check if i>1])
c_s = sum([1 for i in check if i==1])
if c_s>=1 and K<=c_s:
    here = 0
    for _ in range(K):
        here = A[here]
    print(here+1)
else:
    K -= c_s
    here = 0
    for _ in range(c_s + K%c):
        here = A[here]
    print(here+1)

Submission status: Accepted

Solution code:
import sys 
N,K = map(int,input().split())
l = list(map(int,input().split()))
m = [0 for i in range(N)]
location = 0
count = 0
for i in range(K):
    location = l[location] -1
    m[location] += 1
    if m[location] == 2:
        start = location
        for j in range(K-i-1):
            location = l[location] -1
            count += 1
            if location == start:
                for k in range((K-i-j-2)%count):
                    location = l[location] -1
                print(location + 1)
                sys.exit()
        print(location + 1)
        sys.exit()
print(location + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, K = Scanner.map_int()
    A = Scanner.map_int()
    A = [a - 1 for a in A]
    X = 1
    visited = [0 for _ in range(N)]
    p = 0
    while visited[p] == 0:
        visited[p] = X
        X += 1
        p = A[p]
        if X - 1 == K:
            print(p + 1)
            return
    Y = (visited[p] - 1)
    Z = X - Y - 1
    t = (K - Y) // Z
    K -= t * Z
    print(visited.index(K + 1) + 1)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dic = {}
for i, a in enumerate(a_lst):
    dic[i+1] = a

roop = []
visit = [0] * (n + 1)
cur = 1
while visit[cur] != 1:
    visit[cur] = 1
    roop.append(cur)
    cur = dic[cur]   
    
if roop.index(cur) > k:
    print(roop[k])
else:
    roop_length = len(roop) - roop.index(cur)
    rep = roop[roop.index(cur):]
    print(rep[(k - roop.index(cur)) % roop_length])

Submission status: Accepted

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

# 何回で1ループするか
i = 0
done_dict = {i: -1 for i in range(N)}

route_list = []
route_len = 0
step = 1
while True:
    route_len += 1
    done_dict[i] = step
    route_list.append(i)
    next_i = a_list[i] - 1

    if done_dict[next_i] != -1:
        loop_end_i = i
        loop_start_i = next_i
        # print("loop_end_i: " + str(loop_end_i))
        # print("loop_start_i: " + str(loop_start_i))

        first_route_step = step
        # ループのステップ数
        # print("{} -> {}".format(done_dict[loop_start_i], done_dict[loop_end_i]))
        loop_len = done_dict[loop_end_i] - done_dict[loop_start_i] + 1
        # print("loop_len:" + str(loop_len))
        # print(route_list)
        break
    step += 1
    i = next_i

if K < first_route_step:
    ans = route_list[K] + 1
else:
    k = K - first_route_step
    k = k % loop_len
    ans = route_list[done_dict[loop_start_i] - 1 + k] + 1


print(ans)

Submission status: Accepted

Solution code:
int1 = lambda s: int(s)-1

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

X = []
visited = set()
now = 0
while now not in visited:
    visited.add(now)
    X.append(now)
    now = A[now]

if K < len(X):
    print(X[K] + 1)
else:
    s = X.index(now)
    print(X[s + ((K - s) % (len(X) - s))] + 1)

Submission status: Accepted

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

visited = {1: 0}
index = 0
last = 1

for i in range(K):
    t = A[last - 1]
    index += 1
    if t in visited:
        z = K - i - 1
        l = index - visited[t]
        print([k for k, v in visited.items() if v == visited[t] + (z % l)][0])
        exit()
    else:
        visited[t] = index
        last = t

print(last)

Submission status: Accepted

Solution code:
N,K= map(int, input().split())
flags = [-1]*N
M = 1
mods = []
mods.append(0)
A = list(map(int,input().split()))
now = 0
I = 0
flags[0] = 0
if K < 1000000:
    for i in range(K):
        now = A[now] -1

    print(now+1)
else:
        
    for i in range(N):
        now = A[now]-1
        
        
        if flags[now]!=-1:
            I = i
            M=i+1-flags[now]
            break
        mods.append(now)
        flags[now] = i+1

    I += 1
    alt = mods[I-M:]

    if K-I<=0:
        print(now+1)
    else:
        print(alt[(K-I)%(len(alt))]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False for _ in range(N)]

i = 1
c = 0
jun = []

if K <= N:
    while True:
        K -= 1
        i = A[i-1]
        if K == 0:
            print(i)
            exit()


while True:
    if i == A[i-1]:
        print(i)
        exit()
    if visited[i-1]:
        lp = i
        break
    else:
        visited[i - 1] = True
        jun.append(i)
        i = A[i-1]
        c += 1
ji = jun.index(lp)
K -= len(jun[:ji])
jun = jun[ji:]

kai = K % len(jun)
if kai == len(jun):
    print(jun[0])
else:
    print(jun[kai])

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, k = MI()
    al = LI()

    al.insert(0, 0)
    now = 1
    if n >= k:
        for _ in range(k):
            now = al[now]
    else:
        passed = [-1] * (n + 1)
        i = 0
        while passed[now] == -1:
            passed[now] = i
            now = al[now]
            i += 1

        loop = i - passed[now]

        for _ in range((k - passed[now]) % loop):
            now = al[now]

    print(now)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
pos = 1
if k < n:
    for _ in range(k):
        pos = a[pos - 1]
    print(pos)
else:
    lst = [1]
    for _ in range(n):
        pos = a[pos-1] 
        lst.append(pos)
    
    count = 0
    for num, i in enumerate(lst):
        if i == pos and count == 1:
            loop = num - before
            rem = (k - before) % loop
            print(lst[before + rem])
            break
        elif i == pos:
            count = 1
            before = num

Submission status: Accepted

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

dic = {1: 1}
dis = [1]
position = 0
for i in range(len(A_list)):
    if A_list[position] not in dic:
        dic[A_list[position]] = 1
        dis.append(A_list[position])

    else:
        dis.append(A_list[position])
        break
    position = A_list[position] - 1

# print(dic)
temp = dis.index(dis[-1])
# print(temp)
if K <= temp:
    print(dis[K])
    exit()
loop = len(dis) - temp - 1

#print(dis, loop)
K -= len(dis) - (loop + 1)
# print(K)

loop_list = dis[temp:]
# print(loop_list)
loop_temp = K % loop
# print(loop_temp)
print(loop_list[loop_temp])

Submission status: Accepted

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

ima = 0
here = 0

b = ['']*n

while True:

  b[here]=ima
  ima += 1
  here = a[here]-1
 
  if b[here] != '':
    y = ima - b[here]
    x,z = divmod( (k - ima) , y)
#    print(ima)
    ima =  ima + (x * y)
    b = ['']*n
#    print(ima , k , x , y)
  if ima == k:
    break
      
print(here+1)