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: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    #ループしたらそのループの周期でKを割る。

    loop = {i:-1 for i in range(N)}
    loop[0] = 0
    position = 0

    for i in range(N):
        position = A[position] - 1
        if loop[position] != -1:
            ini = loop[position]
            cycle = i+1 - ini
            break
        else:
            loop[position] = i

    M = (K-ini) % cycle

    answer = 0
    for j in range(M):
        answer = A[answer] -1

    answer += 1
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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(1, logk):
    for j in range(n):
        doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
index = 0
k_bin = list(map(int, [list(bin(k))[-i] for i in range(1, logk + 1)]))
for i in reversed(k_bin):
    index = doubling[i][index]
print(index + 1)

Submission status: Wrong Answer

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(1, logk):
    for j in range(n):
        doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
index = 0
k_bin = list(map(int, [list(bin(k))[-i] for i in range(1, logk + 1)]))
for i in k_bin:
    index = doubling[i][index]
print(index + 1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import math,sys
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
import bisect as bi
import heapq 

'''
#------------------PYPY FAst I/o--------------------------------#
 
def I():return (int(stdin.readline()))
def In():return(map(int,stdin.readline().split()))
'''
#------------------Sublime--------------------------------------#
 
#sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
def I():return (int(input()))
def In():return(map(int,input().split()))



def main():
    try:
        n,k=In()
        l=[0]+list(In())
        ans=1
        z=[1]
        rep=[]
        for i in range(n):
            ans=l[ans]
            if ans not in z:
                z.append(ans)
            else:
                if ans not in rep:
                    rep.append(ans)
                else:
                    break
        #print(rep)
        #print(z)
        k-=(len(z)-len(rep))
        #print(k%len(rep))
        print(rep[k%(len(rep))])
        #print(ans)

    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    for _ in range(1):
        main()

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict()
v = defaultdict()

for i in range(1,n+1):
    d[i] = a[i - 1]
    v[i] = False

town = 1
cycle = 0
while cycle < k:
    cycle += 1
    if v[town]:
        k2 = k%cycle
        while k2 > 0:
            k2-=1
            town = d[town]
            break
        break
    town = d[town]
    v[town] = True
    

print(town)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import math,sys
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
import bisect as bi
import heapq 

'''
#------------------PYPY FAst I/o--------------------------------#
 
def I():return (int(stdin.readline()))
def In():return(map(int,stdin.readline().split()))
'''
#------------------Sublime--------------------------------------#
 
#sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
def I():return (int(input()))
def In():return(map(int,input().split()))



def main():
    try:
        n,k=In()
        l=[0]+list(In())
        ans=1
        z=[1]
        rep=[]
        for i in range(k):
            ans=l[ans]
            if ans not in z:
                z.append(ans)
            else:
                if ans not in rep:
                    rep.append(ans)
                else:
                    break
        #print(rep)
        #print(z)
        k-=(len(z)-len(rep))
        #print(k%len(rep))
        print(rep[k%(len(rep))])
        #print(ans)

    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    for _ in range(1):
        main()

Submission status: Wrong Answer

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 % (now - time[curr])
print(time.index(idx))

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
A = [int(i)-1 for i in input().split()]
place = [0]
for _ in range(N):
    place.append(A[place[-1]])
a = place.index(place[-1])
K = a + (K-a)%(N-a)
print(A[K]+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
res= []
t = a[0]
while t not in res:
    res.append(t)
    t = a[t-1]
b = res.index(t)
c = (k-b)%(len(res)-b)
res_0 = res[b:]
print(res_0[c-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
t = k % n
print(a[a[t-1]-1])

Submission status: Wrong Answer

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

place = [0]

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

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

Submission status: Wrong Answer

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
  id=nx+(k-kai[nx])%T
  ans=a[id]+1
print(ans)

Submission status: Wrong Answer

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
  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
  id=kai[nx]+(k-kai[nx])%T
  ans=a[id]+1
print(ans)

Submission status: Wrong Answer

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
  ans=nx
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
  id=kai[nx]+(k-kai[nx])%T
  ans=a[id]+1
print(ans)

Submission status: Wrong Answer

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
  ans=nx
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
  id=kai[nx]+(k-kai[nx])%T
  ans=a[id]+1
print(ans)

Submission status: Wrong Answer

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回移動
        print(i)
        now = dp[i][now] #nowから2^iだけ移動する
        k -= 2 ** i
print(now)

Submission status: Wrong Answer

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:]
	#print(bin_str)
	bin_str[::-1]
	ans = 0
	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: Wrong Answer

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:]
	print(bin_str)
	bin_str[::-1]
	ans = 0
	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: Wrong Answer

Solution code:
n, k = map(int, input().split())
nodes = list(map(int, input().split()))
flgs = [0] * n
now = 1
for i in range(n*3):
    flgs[now-1] += 1
    now = nodes[now-1]
need_noods_for_loop = sum(x > 1 for x in flgs)
need_noods_for_loop = 0
ll = []
l_n = []
for i in range(len(flgs)):
    if flgs[i] > 1:
        need_noods_for_loop += 1
        l_n.append(nodes[i])
        ll.append(1)
    else:
        ll.append(0)

now = 1
cnt = 0
start_node = 0
for i in range(n):
    if ll[now-1] == 1:
        start_node = now
        break
    cnt += 1
    now = nodes[now-1]
k -= cnt
ss = k % need_noods_for_loop
now = start_node
for i in range(ss):
    now = nodes[now-1]
print(now)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = [int(x) for x in raw_input().split()]
    a = [int(x) for x in raw_input().split()]
    visited = [False] * n
    ans = 1
    visited[ans-1] = True
    m = 0
    for x in xrange (k):
        ans = a[ans-1]
        m += 1
        if visited[ans-1]:
            break
        else:
            visited[ans-1] = True
    for x in xrange (k % m - 1):
        ans = a[ans-1]
    print ans
main()

Submission status: Wrong Answer

Solution code:
#
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)
visited={}
l=[0]
i=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-1<=len(l1):
    print(l1[k])
else:
    k-=(len(l1)-1)
    idx=k%len(l2)
    print(l2[idx])

Submission status: Wrong Answer

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]

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

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    #ループしたらそのループの周期でKを割る。

    loop = [0] * (N+1)
    position = 0
    for i in range(N+1):
        position = A[position] - 1
        if position in loop:
            ini = loop.index(position)
            cycle = i+1 - ini
            break
        else:
            loop[i+1] = position
    M = (K-ini) % cycle

    print(loop[(ini+M)] + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

def Search(pos, D):
  global L
  if pos - 1 not in L:
    L[D] = (pos - 1)
    Search(A[pos-1], D + 1)
  else:
    L[D] = (pos - 1)
    L = L[:D+1]
    return pos
  
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [-1] * (N + 1)
#print(L)
Search(1, 0)
#print(L)
if K < L.index(L[-1]):
  print(L[K])
else:
  t = L.index(L[-1])
  k = len(L) - t - 1
  K -= t
  #print(t, k, K % k)
  print(L[t + (K % k)] + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)

def Search(pos, D):
  global L
  if pos - 1 not in L:
    L[D] = (pos - 1)
    Search(A[pos-1], D + 1)
  else:
    L[D] = (pos - 1)
    L = L[:D+1]
    return pos
  
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [-1] * (N + 1)
#print(L)
Search(1, 0)
print(L)
if K < L.index(L[-1]):
  print(L[K])
else:
  t = L.index(L[-1])
  k = len(L) - t - 1
  K -= t
  #print(t, k, K % k)
  print(L[t + (K % k)] + 1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,(input().split()))
A=list(map(int,input().split()))
A.insert(0,0)
loc=1
log=[0]
loop_flg=0
i=0
while(i<=K+2):
  if(loc not in log):
    log.append(loc)
  elif(loc in log and loop_flg==0):
    loop_longth=i-log.index(loc)+1
    K = i+((K-i)%loop_longth)
    loop_flg=1
  loc=A[loc]

  i+=1
print(loc)

Submission status: Wrong Answer

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 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: Wrong Answer

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 a[po-1] == a[po_a-1]:
        flag = 1

flag = 0
cont_topo = 0
po_temp = 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: Wrong Answer

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 = 0

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

k_mod = k % cont

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

print(ans)

Submission status: Wrong Answer

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

visited = [0] * n
i = 0
now = 0
flg = 1
while flg:
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now] 
    else:
        lp = (i + 1) - visited[now]
        st = i - lp
        k_bk = k - st
        k_bk = k_bk // lp
        lft = k - (k_bk * lp + st)
        if lft ==0:
            print(now+1)
        else:
            for _ in range(lft):
                now = lst[now]
            print(now+1)
        break

Submission status: Wrong Answer

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

visited = [0] * n
i = 0
now = 0
while True:
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now] 
    else:
        lp = (i + 1) - visited[now]
        st = i - lp
        k_bk = k - st
        k_bk = k_bk // lp
        lft = k - (k_bk * lp + st)
        if lft ==0:
            print(now+1)
        else:
            for _ in range(lft):
                now = lst[now]
            print(now+1)
        break

Submission status: Wrong Answer

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

visited = [0] * n
i = 0
now = 0
while not all(visited):
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now] 
    else:
        lp = (i + 1) - visited[now]
        st = i - lp
        k_bk = k - st
        k_bk = k_bk // lp
        lft = k - (k_bk * lp + st)
        if lft ==0:
            print(now+1)
        else:
            for _ in range(lft):
                now = lst[now]
            print(now+1)
        break

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    #ループしたらそのループの周期でKを割る。
    import numpy as np
    loop = np.zeros(N+1, int)
    position = 0
    for i in range(N):
        position = A[position] - 1
        if position in loop:
            ini = np.where(loop == position)[0][0]
            cycle = i+1 - ini
            break
        else:
            loop[i+1] = position
    M = (K-ini) % cycle

    print(loop[(ini+M)] + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
#coding :utf-8

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: Wrong Answer

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)
k -= offset
k %= csize + 1
print(cycle[offset + k])