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 = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

cnt = [0]*(2*10**5)#何回出たか
cnt2 = [0]*(2*10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(2*10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        loop = i - cnt2[nxt]
        modC = cnt2[nxt]
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop

if k < modC:
    print(t[k] + 1)
else:
    print(t[modC + modK] + 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

cnt = [0]*(2*10**5)#何回出たか
cnt2 = [0]*(2*10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(2*10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        # print("i: " + str(i))
        # print("nxt: " + str(nxt))
        loop = i - cnt2[nxt]
        modC = cnt2[nxt]
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop
# print("-------")
# print(t)
# print("modC: " + str(modC))
# print("modK: " + str(modK))
# print("loop: " + str(loop))
# print(modK)
# print(loop)
# print("-------")

if k < modC:
    print(t[k] + 1)
else:
    print(t[modC + modK] + 1)

"""
発想はあってる
テストケース公開されたら試してみる！
"""

Submission status: Accepted

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

def main(n,k,a):
    tbl={}
    for i in range(1,n+1):
        tbl[i]=a[i-1]
    machi=1
    for i in range(k):
        machi=tbl[machi]
    return machi

def main2(n,k,a):
    a.insert(0,0)
    #print(a)
    nvisited=[0 for i in range(n+1)]
    #print(nvisited)
    visited=[]
    current=1
    visited.append(current)
    nvisited[current]+=1
    next=a[current]
    #print('next='+str(next))
    while(nvisited[next]==0):
        current=next
        visited.append(current)
        nvisited[current]+=1
        next=a[current]
    loophead=next
    #print('loophead:'+str(loophead))
    #print('visited'+str(visited))
    beforeloop=visited.index(loophead)
    #print('beforeloop:'+str(beforeloop))
    loop=visited[beforeloop:]
    #print('loop:'+str(loop))
    looplen=len(loop)

    if (k<beforeloop):
        return visited[k+1]
    else:
        return loop[(k-beforeloop)%looplen]

def detectloop(a):
        # loopを検出して
        # loopに入る前に訪れた町リスト:head
        # loop内で訪れる町リスト:loop
        # を返す
    nvisit=[0 for i in range(len(a))]
    visited=[]
    n=a[0]
    while(nvisit[n-1]==0):
        nvisit[n-1]+=1
        visited.append(n)
        n=a[n-1]
    #print(visited,n)
    i=visited.index(n)
    #print(i)
    if(i==0):
        loop=visited[:]
        head=[]
    else:
        loop=visited[i:]
        head=visited[:i]
    return head,loop

def main3(n,k,a):
    head,loop=detectloop(a)
    #print(head,loop,k)
    if(k<=len(head)):
        return head[k-1]
    else:
        return loop[(k-len(head))%len(loop) -1]





if __name__=='__main__':
    n,k,a=readinput()
    ans=main3(n,k,a)
    print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))
time = [-1] * (N + 1)
curr = 1
time[curr] = 0
now = 0
while True:
  now += 1
  curr = A[curr]
  if time[curr] >= 0:
    break
  if now == K:
    print(curr)
    exit()
  time[curr] = now

# K = time[curr] + loop * (now - time[curr]) + r
idx = (K - time[curr]) % (now - time[curr])
print(time.index(idx + time[curr]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
for i in range(N-1):
  g.append(t[g[i]-1])
if K>len(g):
  a=g.index(g[-1])
  b=len(g)-a-1
  K=(K-a)%b+a
print(g[K])

Submission status: Accepted

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

lt = [0] + [int(x) for x in input().split()]
#print(lt)
h={1}
g=[1]
for _ in range(n):
    x = lt[g[-1]]
    g.append(x)
    if x in h:
        break
    h.add(x)
#print(g)
if k > len(g):
    i  = g.index(g[-1])
    b = len(g) - i - 1 
    k = (k-i)%b + i
print(g[k])

Submission status: Accepted

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

t=[1]

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

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

loop_end=n
loop_start=n-1

while t[loop_start]!=t[loop_end]:
    loop_start-=1

cycle=loop_end-loop_start
k%=cycle

while k<n+1:
    k+=cycle

print(t[k])

Submission status: Accepted

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

place = [0]
table = [0] * N
table[0] = 1

while True:
    next_place = A_list[place[-1]] - 1
    if table[next_place] == 1:
        idx = place.index(next_place)
        loop = place[idx:]
        break
    table[next_place] = 1
    place.append(next_place)

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

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
t = list(map(int,input().split()))
#t.insert(0,0)
#tmp=1
h={1}
g=[1]
for i in range(N):
    x=t[g[i]-1]
    g.append(x)
    #print(x)
    #print(h)
    if x in h:
        break
    h.add(x)
#print(h,g,x)
if K>len(g):
    a=g.index(g[-1])
    #print(a)
    b=len(g)-a-1
    #print(b)
    K=(K-a)%b+a
print(g[K])

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
kai=[-1 for i in range(n)]
nx=0
now=0
kai[0]=0

if k<=n:
  for i in range(k):
    nx=a[now]
    now=nx
    #print(nx)
  ans=nx+1
else:
  for i in range(n):
    nx=a[now]
    if kai[nx]==-1:
      kai[nx]=i+1
      now=nx
    else:
      T=i+1-kai[nx]
      break
  times=kai[nx]+(k-kai[nx])%T
  now=0
  nx=0
  for i in range(times):
    nx=a[now]
    now=nx
    #print(nx)
  ans=nx+1
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
h={1}
for i in range(N-1):
  x=t[g[i]-1]
  g.append(x)
  if x in h:
    break
  h.add(x)
if K>len(g):
  a=g.index(g[-1])
  b=len(g)-a-1
  K=(K-a)%b+a
print(g[K])

Submission status: Accepted

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

visited = [-1 for i in range(N)]
count = 0
cycle_start = -1
now = 0
trav_length, cycle_length = 0, 0

while True:
    if visited[now] != -1:
        cycle_start = now
        cycle_length = count - visited[now]
        break
    visited[now] = count
    now = A[now] - 1
    trav_length += 1
    count += 1


to_cycle_length = trav_length - cycle_length

if K <= N:
    now = 1
    while K > 0:
        K -= 1
        now = A[now - 1]
    print(now)
else:
    K -= to_cycle_length
    K %= cycle_length
    now = cycle_start + 1
    while K > 0:
        K -= 1
        now = A[now - 1]
    print(now)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	daburu = []
	tmp = []
	for a in A:
		tmp.append(a-1)
	daburu.append(tmp)
	ima = 2
	while True:
		if ima > K:
			break
		sample = daburu[-1]
		next = []
		for i in range(N):
			tmp = sample[i]
			next.append(sample[tmp])
		daburu.append(next)
		ima *= 2

	bin_str = bin(K)
	bin_str = bin_str[2:]
	bin_str = bin_str[::-1]
	ans = 0
	#print(bin_str)
	for i,val in enumerate(bin_str):
		#print(ans)
		if val == "1":
			ans = daburu[i][ans]

	#print(daburu)
	print(ans+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

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

p=1
if k<=n:
  for i in range(k):
    p=a[p-1]
  print(p)
  exit()

t=[-1]*n
t[0]=0
for i in range(1,n):
  p=a[p-1]
  if t[p-1] !=-1:
    break
  t[p-1]=i

d=i-t[p-1]
k-=i
k%=d
for i in range(k):
  p=a[p-1]
print(p)

Submission status: Accepted

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

o = [0] * 63

def bi(x):
    i = 0
    while x != 0:
        o[i] = x%2
        x //= 2
        i += 1

bi(K)

n = 0
for i in range(63):
    if o[i]:
        n = A[n]
    for j in range(N):
        B[j] = A[A[j]]
    for j in range(N):
        A[j] = B[j]
        
print(n+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [0] + a
dp = [a] #dp[k][i]はiから2^k回移動した後にいる町の番号
for x in range(1,60):#2^0～2^100回まで移動した
    dp.append([0]) #先頭を0に
    for i in range(1,n+1):
        j = dp[x-1][i] #k-1回移動した後にいる場所
        dp[x].append(dp[x-1][j])

now = 1

for i in range(60):
    if k & 2 ** i > 0: #k=5(101)の場合1回移動してから4回移動
        now = dp[i][now] #nowから2^iだけ移動する
        k -= 2 ** i
print(now)

Submission status: Accepted

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

ma = [0]*N
pr = [0]*N
flag = 0
i = 0
ne = A[i]
#print(1)
ma[i] = 1
pr[i] = 1
#print(ne)

while(flag == 0):
  #map判定
  if(ma[ne-1] == 0):
    ma[ne-1] = 1
    pr[ne-1] = i+2
  else:
    #print('flag!')
    flag = 1
    break
  
  #Kに到達(ループなし)
  if(i == K-1):
    #print('fin!')
    flag = 2
    break
  
  #更新
  ne = A[ne-1]
  i+=1
  #print(ne)

#print('---')
if(flag == 1):
  #calc
  start = pr[ne-1]
  #print('start = '+str(start))
  dist = i+2 - start
  #print('dist = '+str(dist))
  
  tmp = (K-start)%dist + start
  #print('tmp = '+str(tmp))
  
  #print(pr)
  ind = pr.index(tmp)
  #print('ind = '+str(ind))
  ne = A[ind]
  #for x in range(N):
  #  if(pr[x] == tmp):
  #    ne = A[x]

print(ne)
#print(pr)
#print(ma)

Submission status: Accepted

Solution code:
#
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)
visited={}
l=[0]
i=a[1]
while True:
    if visited.get(i,False)==False:
        visited[i]=True
        l.append(i)
        i=a[i]
    else:
        index=l.index(i)
        l1=l[0:index]
        l2=l[index:]
        #print(i,l1,l2)
        break
#print(l1,l2)
if k<=len(l1)-1:
    print(l1[k])
else:
    if len(l1)>1:
        k-=(len(l1)-1)
    idx=(k-1)%len(l2)
    print(l2[idx])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
#"tel"は既に訪れている町
tel = set()
route = []
#"town"は今いる町
town = 1
route.append(town)
tel.add(town)
time_loop = 0
for i in range(k):
    town = a[town-1]
    if town in tel:
        time_loop += 1
        break
    tel.add(town)
    route.append(town)
    #テレポートした回数をカウント
    time_loop += 1

#"start"は"route"内のループの起点のとなる町のインデックス番号
start = route.index(town)
if time_loop != start:
    k = (k - start) % (time_loop - start)
    print(route[k+start])
else:
    print(town)

Submission status: Accepted

Solution code:
#n=int(input())
n,k=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

trans=[1]
dic={}
bef=1
dic[bef]=0
for i in range(n):
    trans.append(al[bef-1])
    bef=trans[-1]
    if dic.get(bef,-1)>=0:
        st=dic[bef]
        ed=i
        break
    dic[bef]=i+1
pattern=trans[st:ed+1]
until_num=st
if k<st:
    ans=trans[k]
else:
    ans=pattern[(k-st)%(ed-st+1)]
print(ans)

Submission status: Accepted

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

p=1
if k<=n:
  for i in range(k):
    p=a[p-1]
  print(p)
  exit()

t=[-1]*n
t[0]=0
for i in range(1,n):
  p=a[p-1]
  if t[p-1] !=-1:
    break
  t[p-1]=i

d=i-t[p-1]
k-=i
k%=d
for i in range(k):
  p=a[p-1]
print(p)

Submission status: Accepted

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

po_a = 1
po_b = 1
flag = 0

while flag != 2:
    if flag == 0:
        po_a = a[po_a-1]
        po_b = a[po_b-1]
        po_b = a[po_b-1]
        if po_a == po_b:
            flag += 1
            po_b = 1
    else:
        po_a = a[po_a-1]
        po_b = a[po_b-1]
        if po_a == po_b:
            flag += 1

flag = 0
po = po_a
cont_po = 0

while flag != 1:
    po = a[po-1]
    cont_po += 1
    if po == po_a:
        flag = 1

flag = 0
cont_topo = 0
po_temp = 1

if k <= 2*(10**5):
    for i in range(k):
        ans = a[ans-1]
else:
    if po_a != 1:
        while flag != 1:
            ans = a[ans-1]
            cont_topo += 1
            if ans == po_a:
                flag = 1

    k_cont = k-cont_topo
    k_cont = k_cont%cont_po

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


print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
a = [i - 1 for i in list(map(int, input().split()))]
logK = K.bit_length()
doubling = [[-1 for _ in range(N)] for _ in range(logK)]
for i in range(N):
    doubling[0][i] = a[i]
for i in range(logK - 1):
    for j in range(N):
        doubling[i + 1][j] = doubling[i][doubling[i][j]]
now, i = 0, 0
while K > 0:
    if (K & 1):
        now = doubling[i][now]
    K = K >> 1
    i += 1
print(now + 1)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
a = [i - 1 for i in list(map(int, input().split()))]
logK = 1
while ((1 << logK) < K):
    logK += 1
doubling = [[-1 for _ in range(N)] for _ in range(logK)]
for i in range(N):
    doubling[0][i] = a[i]
for i in range(logK - 1):
    for j in range(N):
        doubling[i + 1][j] = doubling[i][doubling[i][j]]
now, i = 0, 0
while K > 0:
    if (K & 1):
        now = doubling[i][now]
    K = K >> 1
    i += 1
print(now + 1)

Submission status: Accepted

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

if K<=N:
  p=0
  for i in range(K):
    p=A[p]
  print(p+1)
  exit()
p=0
t=[-1]*N
t[0]=0
for i in range(1,N):
  p=A[p]
  if t[p] !=-1:
    break
  t[p]=i

d=i-t[p]
K-=i
K%=d
for i in range(K):
  p=A[p]
print(p+1)

Submission status: Accepted

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

count_dict = {i+1:0 for i in range(n)}
count_dict[1] = 1

anow = 1
if k <= n+1:
  for i in range(k):
    anow = a[anow]
  print(anow)
else:
  for i in range(2, n+3):
    anow = a[anow]
    cnow = count_dict[anow]
    if cnow != 0:
      cycle = i-cnow
      amari = (k-i+1)%cycle
      if amari==0:
        print(anow)
      else:
        for nokori in range(amari):
          anow = a[anow]
        print(anow)
      exit()
    else:
      count_dict[anow] = i

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
s=1
M=[0]
B=[False]*(n+1)
while cnt<n:
    s=A[s-1]
    if not B[s-1]:
        B[s-1]=True
    else:
        break
    M.append(s-1)
    cnt+=1
x=M.index(s-1)
y=len(M)-x

if k<=x:
    print(M[k]+1)
else:
    N=M[x:]
    print(N[(k-x)%y]+1)

Submission status: Accepted

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

# D - Teleporter
def show_town(route, k):
	i = 0
	
	for r in route:
		if i == k:
			print(r)
			break
		else:
			i += 1


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

route = dict()
route[1] = a[0]
town = a[0]

while True:
	if town in route.keys():
		break
	else:
		route[town] = a[town-1]
		town = a[town- 1]

minus = 0

for r in route:
	if r != town:
		minus += 1
	else:
		break

if k < minus:
	show_town(route, k)
else:
	loop_count = len(route) - minus
	#print(minus)
	#print(loop_count)

	remainder = (k - minus) % loop_count
	i = 0
	is_start = False

	for r in route:
		if r == town:
			is_start = True
	
		if is_start == True:
			if i == remainder:
				print(r)
				break
			else:
				i += 1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

cnt=0
now=1
cyc=0
visited=[0]*n
flg=False
for i in range(k):
    cnt+=1
    now=a[now-1]
    visited[now-1]+=1
    if visited[now-1]==2:
        cyc+=1
        #print(cyc)
    if visited[now-1]==3:
        flg=True
        #print(visited,cyc,now)
        #cyc-=1
        break
    #print(visited,now)
#print(cyc, cnt, now, (k-cnt+2*cyc) % cyc)
if flg:
    for i in range((k-cnt+2*cyc)%cyc):
        now=a[now-1]
    print(now)
else:
    print(now)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
n , k = map(int , input().split())
arr = list(map(int , input().split()))
dic = defaultdict(int)
for i in range(1,n+1):
	dic[i] = arr[i-1]
cycle = []
visited = [False]*(10**6)
curr = 1
while True:
	cycle.append(curr)
	visited[curr] = True
	curr = dic[curr]
	#k -= 1
	if visited[curr]:
		break

csize = 0
ind = 0
for i in range(len(cycle)-1,-1,-1):
	if cycle[i] == curr:
		ind = i + 1
		break
	csize += 1
offset = len(cycle) - csize - 1
#print(cycle,csize+1, k , curr,offset)
if k - offset < 0:
	exit(print(cycle[k]))
k -= offset
k %= csize + 1
print(cycle[offset + k])

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
l = list(map(int, input().split()))
count = 0
li = [0 for _ in range(n)]
b = 1
for i in range(1,n + 1):
#     print(b)
    if li[b-1] != 0:
        break
    li[b-1] = i
    b = l[b-1]
    count += 1
#     print('count',count)


d = count - li[b-1] + 1
intercep = li[b-1] -1
# print('d', d, 'intercep', intercep)
if k <= intercep:
    b = 1
    for i in range(k):
        b = l[b-1]
    print(b)
    sys.exit()
    
mod = (k - intercep) % d
b = 1
for i in range(intercep + mod):
#     print('b',b)
    b = l[b-1]
print(b)

Submission status: Accepted

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

a = [0]
a.extend(list(map(int,input().split())))
l = [None]*(n+1)

now = 1
step = 0
l[now] = 0
while k:
    now = a[now]
    step += 1
    k -= 1
    if l[now] is not None:
        looplen = (step - l[now])
        k = k%looplen
    else:
        l[now] = step
print(now)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
dic = {}
for key, a in zip(range(1, n+1), a):
    dic[key] = a
 
log = [-1]*(n+1)
next = dic[1]
step = 1
log[next] = step
k -= 1
while k:
    next = dic[next]
    step += 1
    k -= 1
    if log[next] != -1:
        k %= log[next] - step
    else:
        log[next] = step
print(next)

Submission status: Accepted

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

flag = [False] * n

town = 1
towns = [1]
flag[0] = True

while(True):
    ntown = A[town-1]
    if flag[ntown-1]:
        l_s = towns.index(ntown)
        
        if k < l_s:
            print(towns[k])
            break
        else:
            l = towns[l_s:]
            k -= l_s
            print(l[k%len(l)])
            break
        
    else:
        flag[ntown-1] = True
        towns.append(ntown)
        town = ntown
        
#print(l, l_s)

Submission status: Accepted

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


# nowから2**i先まで移動したとこ
def double(now, i):
    global A
    if A[i][now] != -1:
        return A[i][now]
    # nowから2**(i-1)移動して、そこからさらに2**(i-1)移動する
    A[i][now] = double(double(now, i - 1), i - 1)
    return A[i][now]


# nowからk移動した場所を求める
def rec(now, k):
    if k == 0:
        return now
    log2k = len(bin(k)) - 3
    return rec(double(now, log2k), k - 2 ** log2k)

print(rec(1, K))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
c=1
while K:
  if K&1:
    c=A[c]
  A=[A[A[i]] for i in range(N+1)]
  K>>=1
print(c)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
c=1
while K:
  if K&1:
    c=A[c]
  A=[A[A[i]] for i in range(len(A))]
  K>>=1
print(c)

Submission status: Accepted

Solution code:
nk = [int(s) for s in input().split()]
n, k = nk[0], nk[1]
cities = [int(s) for s in input().split()]
curr_city = 1
F = {1 : [0]}
round = 1
loop = 0
while True:
    curr_city = cities[curr_city-1]
    if curr_city in F:
        F[curr_city].append(round)
        if len(F[curr_city]) >= 3:
            break
    else:
        F[curr_city] = [round]
    round += 1
round = 1
curr_city = 1
while len(F[curr_city]) < 3:
    curr_city = cities[curr_city-1]
    round += 1
    k -= 1
    if k == 0:
        print(curr_city)
        break
    
if k > 0:
    loop = F[curr_city][1]-F[curr_city][0]
    k = k%loop
    while k > 0:
        curr_city = cities[curr_city-1]
        k -= 1
    print(curr_city)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    visited = [0]
    visited_set = {0}
    now = 0
    for i in range(2*n):
        now = a[now]
        if now in visited_set:
            break
        else:
            visited.append(now)
            visited_set.add(now)
    l = len(visited)
    v = visited.index(now)
    if k < v:
        print(visited[k]+1)
    else:
        k -= v
        k %= (l-v)
        k += v
        print(visited[k]+1)


main()

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    g = list(map(int, input().split()))
    disc = [-1]*(n+1)
    s = []
    v = 1
    c = 0
    while disc[v] == -1:
        disc[v] = len(s)
        s.append(v)
        v = g[v-1]
        c = len(s) - disc[v]
    l = len(s)
    if l > k:
        print(s[k])
    else:
        r = (k - disc[v]) % c
        for i in range(r):
            v = g[v-1]
        print(v)
resolve()

Submission status: Accepted

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

visited = [1] + [0] * (N-1)
first_dist = [0] * N
turn = 0
pos = 0

for i in range(N+1):
    if i == K:
        print(pos+1)
        sys.exit()
    turn += 1
    pos = A[pos]
    if visited[pos] :
        loop = turn - first_dist[pos]
        break
    else:
        visited[pos] = 1
        first_dist[pos] = turn

loop_path = [pos]
for i in range(loop):
    pos = A[pos]
    loop_path.append(pos)
pos = loop_path.pop()
print(loop_path[(K - first_dist[pos])%loop] + 1)

Submission status: Accepted

Solution code:
import collections
import numpy as np
import sys
import copy

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):
    A[i]-=1
B=[0]
visited=[0]*N
visited[0]=1
Flag=True
for i in range(0,N*2):
    next=A[B[i]]
    if visited[next]==0:
        B.append(next)
        visited[next]=1
    else:
        C=B[B.index(next):]
        num=B.index(next)
        break
#print(C)
if K>num:
    Ans=(K-num)%len(C)
    print(C[Ans]+1)
else:
    print(B[K]+1)

Submission status: Accepted

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

visited = [False]*(2*10**5 + 10)
val = 1
count = 0
hold = k
while hold > 0 :
    if visited[val - 1] or val == t[val - 1]:
        break
    visited[val - 1] = True
    val = t[val - 1]
    # print('a', val)
    count += 1
    hold -= 1
# print(hold)
if hold == 0:
    print(val)
    exit(0)
if val == t[val - 1]:
    print(val)
    exit(0)
count0 = count
count = 1
newval = val
start = t[newval - 1]
while start != newval:
    count += 1
    start = t[start - 1]
# print('count', count, 'count0', count0)
if t[val - 1] == t[0]:
    temp = k
else:
    temp = k - count0
# print('temp', temp)
jump = (temp) % (count)
# print('jump', jump)
# print('val', val)
ans = val
for i in range(jump):
    ans = t[ans - 1]
    # print('b', ans)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ord_ = [-1] * n # 何回目に訪れたか
homon = [] # 訪問した順番のリスト
current = 0
while ord_[current] == -1:
    ord_[current] = len(homon)
    homon.append(current)
    current = a[current] - 1

freq = len(homon) - ord_[current] # ループする都市数
n_before_loop = ord_[current] # ループするまでの都市数

if k < n_before_loop:
    print(homon[k] + 1)
else:
    k -= n_before_loop
    k %= freq
    print(homon[n_before_loop+k] + 1)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**5*2)

def search(u, n, g, disc, k):
    if disc[u] != None:
        circles = n - disc[u]
        v = (k - disc[u]) % circles
        ans = u
        if n > k:
            ans = 0
            for _ in range(k):
                ans = g[ans]
            return ans + 1
        for i in range(v):
            ans = g[ans]
        return ans + 1
    disc[u] = n
    return search(g[u], n+1, g, disc, k)

def resolve():
    n, k = map(int, input().split())
    g = list(map(lambda x: int(x) - 1, input().split()))
    disc = [None]*n
    v = search(0, 0, g, disc, k)
    print(v)
resolve()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = [a-1 for a in map(int, input().split())]    # 0-indexed に変換
    B = [None]*N    # 何ステップ目に到達したかを記録。Noneなら未到達を表す
    now = 0         # 現在地
    step = 0        # ステップ数
    B[now] = 0      # 開始地点は、0ステップ目に到達済みとする
    while K:
        now = A[now]    # 現在地を更新 
        step += 1
        K -= 1
        if B[now] is not None:  # ループを検出したら...
            K %= (step - B[now])      # Kからループ長さを引けるだけ引く
        else:
            B[now] = step  # 到達したステップ数を記録
    print(now+1)    # 1-indexed に再変換
 
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
X = {1}
r = [1]
for i in range(0, N):
    tmp = A[r[-1]-1]
    if K == 1:
        print(tmp)
        exit(0)
    else:
        if X.isdisjoint({tmp}):
            r.append(tmp)
            X.add(r[-1])
            K -= 1
        else:
            R = r[r.index(tmp):]
            K -= 1
            break
print(R[K % len(R)])

Submission status: Accepted

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

now = 0
i = 1
flg2 = 1
loop = 0
while (i < k+1):
    if (flg2 and flg[a[now]] != 0):
        flg2 = 0
        loop = i-flg[a[now]]
        i += ((k - i) // loop - 1) * loop
    now = a[now]
    flg[now] = i
    i += 1
print(a[now])