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:
N, K = map(int, input().split())
A = list(map(int, input().split()))

loop_checker = [1]
before_loop_len = 0
loop_len = 0

now = 0
while True:
    if A[now] in loop_checker:
        index_val = loop_checker.index(A[now])
        loop_slice = loop_checker[index_val:]
        before_loop_len = loop_checker.index(A[now])
        loop_len = len(loop_slice)
        break
    else:
        loop_checker.append(A[now])
        now = A[now] - 1
if K <= before_loop_len:
    print(A[K])
else:
    checkK_prep = (K - before_loop_len)
    checkK = checkK_prep % loop_len

    print(A[before_loop_len + checkK])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=tuple(map(int,input().split()))
state=[1]
for _ in range(n+1):
    state.append(A[state[-1]-1])
count={}
for i in range(n+1):
    if state[i] in count:
        if i>0 and state[i-1]==state[count[state[i-1]]]:
            start=count[state[i]]
            end=i
    else:
        count[state[i]]=i
k -= start
k%=(end-start)
print(state[k+start])

Submission status: Wrong Answer

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

now_in=0
count=0
for i in range(n):
    now_in=a[now_in]-1
    count+=1
    if now_in==0:
        break

k = k%count

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

now_in +=1
print(now_in)

Submission status: Wrong Answer

Solution code:
import sys
l = sys.stdin.readline().strip()
N, K = map(int, l.split())
l = sys.stdin.readline().strip()
A = [0] + list(map(int, l.split())) 
visited = [-1] * (len(A)+1)

remain = K
crt = 1
entrance = -1
while remain > 0:
    remain -= 1
    # check visited
    if visited[crt] == -1:
        visited[crt] = K - remain
        crt = A[crt]
    else:
        entrance = crt
        crt = A[crt]
        break
print(entrance, remain)

if entrance == -1:
    print(crt)
else:
    loop = (K-remain) - visited[entrance] 
 
    later = remain % loop
    for i in range(later):
        crt = A[crt]
    print(crt)

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)

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

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	tugi = 0
	ans = []
	cnts = 0
	for i in range(K):
		tugi = mati[tugi]
		cnts += 1
		if tugi in ans:
			break
		else:
			ans.append(tugi)

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K+1+cnts) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+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())
A = list(map(int, input().split()))

p = [-1] * N
p[0] = 0
flag = 0
now = 1
i = 0

while flag == 0:
    now = A[now - 1]
    i += 1
    if p[now - 1] != -1:
        flag = 1
    else:
        p[now - 1] = i

r = i - p[now - 1]
e = p[now - 1]

count = K - e
pi = count % r

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

print(now)

Submission status: Wrong Answer

Solution code:
import collections

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

ex = collections.defaultdict(lambda:-1)
step=1
cur=0
ex[0]=0
while 1:
    if ex[a[cur]]!=-1:
        cycle = step-ex[a[cur]]
        k-=ex[a[cur]]-1
        #print(k%cycle)
        break
    else:
        ex[a[cur]]=step
        cur=a[cur]
    step+=1

#print(ex,k%cycle)
for i in range(k%cycle):
    cur = a[cur]
print(cur+1)

Submission status: Wrong Answer

Solution code:
import sys 
n,m=list(map(int,input().split(" ")))
sys.setrecursionlimit(10**6) 
arr=list(map(int,input().split(" ")))
d={}
for i in range(n):
	d[i]=[]
for i in range(n):
	d[i].append(arr[i]-1)

from collections import deque
def bfs(start,n,visited,m):
	# count=0

	# l2=[i+1]
	q=[start]
	q=deque(q)
	# count+=1
	moves=[]
	moves.append(start)
	visited[start]=1
	left=-1
	fl=0
	while (len(q)!=0 and fl==0):
		y=d[q[0]]
		for j in y:
			if(visited[j]==0):
				moves.append(j)
				visited[j]=1
				# l2.append(j)
				q.append(j)

				# count+=1
			else:
				left=j
				fl=1
				break



		q.popleft()
	# print(left,moves)
	if(left!=-1):
		pre=[]
		post=[]
		for i in range(len(moves)):
			if(moves[i]==left):
				pre=moves[:i]
				post=moves[i:]
				break
		if(m<=len(pre)):
			print(pre[m-1]+1)
		else:
			m-=len(pre)

			print(post[m%len(post)]+1)


	else:
		# curr=0

		print(pre[moves%len(pre)])
visited=[0]*n
bfs(0,n,visited,m)

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
ed=[]
d=set()
now=0
x=-1
while True:
    ed.append(now)
    d.add(now)
    ne=A[now]
    if ne in d:
        x=ne
        break
    else:
        now=ne
def ind(l,a):
    for i in range(len(l)):
        if a==l[i]:
            return i
dn=ind(ed,ne)
T=len(ed)-dn
ans=A[dn+(K-dn)%T]
print(ans+1)

Submission status: Wrong Answer

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

pcyc = []
cyc = []
i = 0
while(True):
    if a[i] in pcyc:
        i = a[i]-1
        break
    else:
        i = a[i]-1
        pcyc.append(i+1)

while(True):
    if a[i] in cyc:
        break
    else:
        i = a[i]-1
        cyc.append(i+1)

print(cyc[((k-(len(pcyc)-len(cyc))+1)%len(cyc))])

Submission status: Wrong Answer

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

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

loop = False
count = 0
visited = []
i = 1
while(count != k):
	if i in visited: break
	visited.append(i)
	i = a[i-1]
	count += 1
if(count != k):
	itr = k%count
	print(a[itr])
	# count = 0
	# i = 0
	# while(count != itr):
	# 	i = a[i-1]
	# 	count += 1
	# print(i,visited)
else:
	print(visited[len(visited)-1])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()
for i in range(n):
    a[i] -= 1
ct = [0 for i in range(n)]

def dfs(v):
    nv = a[v]
    if ct[nv] == k:
        return nv, 0
    if ct[nv] != 0 or nv == 0:
        r = ct[v] + 1 - ct[nv]
        l = (k - ct[nv]) % r
        return nv, l
    else:
        ct[nv] = ct[v] + 1
        return dfs(nv)

nv, l = dfs(0)
for i in range(l):
    nv = a[nv]
print(nv + 1)

Submission status: Wrong Answer

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

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


s=[]
sen=1
for i in range(k):
    if(sen in s):
        break
        
    else:
        s.append(sen)
        sen=a[sen-1]

print(s)

k=k%len(s)
if(sen!=1):
    k-=1
#sen=1
for i in range(k):
    sen=a[sen-1]
print(sen)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input('').split(' '))
a=input('')
a=a.split(' ')
for p in range(n):
    a[p]=int(a[p])

p=1
for j in range(k):
    p=a[p-1]-1

print(a[p])

Submission status: Wrong Answer

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

end=0
ans=0

while True:
    i=a[i]-1
    t=a[i]
    print(t)
    if t not in res:
        res.append(t)
    else:
        end=i
        break
l=len(res)
s=res.index(a[end])
r=l-s
if k<l:
    print(res[k])
else:
    k-=s
    ans=k%r + s
    print(res[ans])

Submission status: Wrong Answer

Solution code:
import sys

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

array = [-1] * (n+1)
array[1] = 0

li = []
li.append(1)

tmp = -1
i = 1
index = 0
while True:
  if array[a[index]] != -1:
    tmp = array[a[index]]
    break
    
  if i == k:
    print(a[index])
    sys.exit(0)
    
  li.append(a[index])
  array[index] = i
  index = a[index] -1
  i += 1
  
k -= tmp
d = len(li)

k %= d

print(li[(k+tmp) % d])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split(" "))
a_list = list(map(int,input().split(" ")))
visit = [0 for num in range(n)]
path = [0]
counter = 0
current_point = 0
while True:
    next_point = a_list[current_point]-1
    counter += 1
    if visit[next_point] == 1:
        current_point = next_point
        break
    visit[next_point] = 1
    path.append(next_point)
    current_point = next_point
loop_point = path.index(current_point)
loop_num = counter - loop_point
loop_path = path[loop_point:counter]
if k<loop_point:
    print(path[k+1])
else:
    print(loop_path[(k-loop_point)%loop_num]+1)

Submission status: Wrong Answer

Solution code:

import collections


def solve(n, k, arr):
    visited = set()
    i = 0

    cyclicArr = []
    curr = 0
    while i not in visited:
        visited.add(i)
        cyclicArr.append(i+1)

        i = arr[i]-1
        curr += 1

    cyclicArr.append(i+1)

    lastDigit = cyclicArr[-1]
    m = len(cyclicArr)

    j = 0

    if lastDigit == 1:
        newCyclicArray = cyclicArr[1:]
    else:
        while j < m and cyclicArr[j] != lastDigit:
            k -= 1
            j += 1

        newCyclicArray = cyclicArr[j+1:]

    dex = k % len(newCyclicArray)

    # print("Cyclic Array: {}".format(cyclicArr))
    # print("New Cyclic Array: {}".format(newCyclicArray))
    # print("Dex-1: {}, k: {}".format(dex-1, k))

    return newCyclicArray[dex-1]


[n, k] = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))

print(solve(n, k, arr))

Submission status: Wrong Answer

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

#インデックスを1オリジンに
A.insert(0,-1)

accessed_node = [1]
loop_root = []
loop_madeno_size = 0
loop_size=0
t=1
#ループ検出
for i in range(1,len(A)):
  if not A[t] in accessed_node:
    accessed_node.append(A[t])
    #次の場所を決める
    t=A[t]
  else:
    #ループ路を確定する
    loop_start_index=accessed_node.index(A[t])
    loop_root = accessed_node[loop_start_index:]
    loop_madeno_size = loop_start_index
    loop_size=len(loop_root)
    break
#print(accessed_node)
#print(loop_madeno_size)
K -= loop_madeno_size
print(loop_root[K%loop_size])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI_()
    d = defaultdict(int)
    i = a[0]
    t = 0
    d[0] = 0
    while not d[i]:
        t += 1
        d[i] = t
        i = a[i]
    t += 1
    if t >= k:
        i = 0
        for _ in range(k):
            i = d[i]
        print(i + 1)
    else:
        k -= d[i]
        k %= (t - d[i])
        for _ in range(k):
            i = a[i]
        print(i + 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, K = map(int,input().split())
A = list(map(int, input().split())) 
check = [0]*N
tele_lis = []
global start
start = []
def tele(x):
    check[x-1] = 1
    tele_lis.append(x)
    if check[A[x-1]-1] == 0:
        tele(A[x-1])
    else:
        start.append(A[x-1])
        return
tele(1)
for i in range(N):
    if start[0] == tele_lis[i]:
        break
    
print(tele_lis[i::][(K-i) % (sum(check)-i)])

Submission status: Wrong Answer

Solution code:
# @author 

import sys

class DTeleporter:
    def solve(self, tc=0):
        n, k = [int(_) for _ in input().split()]
        a = [int(_) - 1 for _ in input().split()]
        done = dict()
        cur = 0
        steps = 0
        while cur not in done and steps < k:
            done[cur] = steps
            cur = a[cur]
            steps += 1
        
        if steps == k:
            print(cur)
            return
        
        d = steps - done[cur]
        steps = steps + ((k - steps) // d) * d

        while steps < k:
            cur = a[cur]
            steps += 1

        print(cur + 1)


solver = DTeleporter()
input = sys.stdin.readline

solver.solve()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
check = [-1]*n
cntr = 0
que = deque([0])
while que:
    x = que.popleft()
    if check[x] != -1:
        break
    check[x] = cntr
    cntr += 1
    que.append(a[x]-1)
c = check[x]
d = cntr - c
check = [-1]*n
cntr = 0
que = deque([x])
while que:
    x = que.popleft()
    if check[x] != -1:
        break
    check[x] = cntr
    cntr += 1
    que.append(a[x]-1)
for i in range(n):
    if check[i] == (k-c) % cntr:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import collections

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

ex = collections.defaultdict(lambda:-1)
step=1
cur=0
ex[0]=0
while 1:
    if ex[a[cur]]!=-1:
        cycle = step-ex[a[cur]]
        k-=ex[a[cur]]-1
        #print(k%cycle)
        break
    else:
        ex[a[cur]]=step
        cur=a[cur]
    step+=1

print(ex,k%cycle)
for i in range(k%cycle):
    cur = a[cur]
print(cur+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
board = [-1 for _ in range(N)]
now = 1
for i in range(1, N+1):
    if board[now-1] == -1:
        board[now-1] = i
        now = A[now-1]
    else:
        loop = i - board[now-1]
        init = board[now-1] - 1
        break
K -= init
if K < 0:
    K = init
else:
    K = K % loop

for i in range(N):
    if board[i] - init == K + 1:
        print(i+1)
        break

Submission status: Wrong Answer

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

now=0

been = [0]*n
been[0]=1
for i in range(n):
    now=a[now]
    if been[now]==0:
        been[now]=1
    else:
        t_stack=sum(been)
        break

start=now

been = [0]*n
been[now]=1
for i in range(n):
    now=a[now]
    if been[now]==0:
        been[now]=1
    else:
        period=sum(been)
        break

now=start
for i in range((k-(t_stack-period))%period):
    now=a[now]
print(now+1)

Submission status: Wrong Answer

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

s = 1
cost = -1
while True:
    g = lis[s-1]
    cost += 1
    if lis_cost[s-1] == -1:
        lis_cost[s-1] = cost
        s = g
        lis_root.append(g)
    else:
        break
    #print(lis_cost)
    
#print(cost,s) # cost回目のジャンプでs番目に着いた

cost_loop = cost-lis_cost[s-1]
cost_prev = lis_cost[s-1]
lis_root = lis_root[cost_prev:-1]
#print(cost_loop,cost_prev,lis_root)

q = (K-cost_prev+1)%len(lis_root)
if q==0:
    print(lis_root[-1])
else:
    print(lis_root[q-1])

Submission status: Wrong Answer

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

A0=list(range(N))
temp=0

for i in range(N):
  temp=A[i]

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
roop=[]
roop_set=set([])

a.insert(0, 0)
s=1
for i in range(k):
    s=a[s]
    if(s not in roop_set):
        roop.append(s)
        roop_set.add(s)
    else:
        s_first=roop.index(s)
        roop=roop[s_first:]
        k-=(s_first+1)
#        print(k,roop,s_first)
        print(roop[k%len(roop)])
        break

Submission status: Wrong Answer

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

vst = [False for i in range(N)]
plc = [0]

for i in range(N):
    mm = plc[-1]
    mm2 = A[mm]-1
    if vst[mm2]:
        break
    vst[mm] = True
    plc.append(A[mm]-1)

li = []
flg = False
for i in range(len(plc)):
    if plc[i]==mm2:
        flg = True

    if not(flg):
        continue

    li.append(plc[i])

# for i in A:
#     print(i-1," ",end="")


ans = (K-len(plc))%len(li)
if ans >=0:
    print(li[ans]+1)
else:
    print(plc[K]+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=1
sa=set()
d=dict()
count=0
niko=0
while True:
  count+=1
  if not (a[s-1] in sa):
    sa.add(a[s-1])
    d[a[s-1]]=count
    s=a[s-1]
    
  else:
    niko=a[s-1]
    number=count-d[a[s-1]]
    break
    
lf=False
ans_list=[]
kaisu=0
for i,j in d.items():
  if i==niko:
    lf=True
    kaisu=j
  if lf==True:
    ans_list.append(i)
print(ans_list[(k-kaisu)%number])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
seen = [False]*N
seen[0] = True
loop = [0]
is_same = False
is_same_idx = 0
while True:
    nxt_i = A[loop[-1]] # 1-indexed
    # if A[nxt_i-1]-1 == loop[-1]:
    #     is_same = True
    #     is_same_idx = len(loop)

    if not seen[nxt_i-1]:
        seen[nxt_i-1] = True
    else:
        break
    loop.append(nxt_i-1)


#print(loop)

if loop[-1] == A[loop[-1]]: # 以降ずっとループ
    if K >= len(loop):
        print(loop[-1])
        exit()
        #print('a')

ans_i = K%len(loop)
ans = A[ans_i]
#print('idx',ans_i)
print(ans)

Submission status: Wrong Answer

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

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

# ループがあるか見つけ、ループのサイズを見つける
# ループしている場合、残りのｋをループで割ったあまりに置き換える
INF = 10**12
cnt = [-1 for _ in range(n)]
cur = 0
size = INF
idx = 0
for i in range(k):
    if cnt[cur] != -1:
        size = i - cnt[cur]
        idx = i
        break
    cnt[cur] = i
    next_idx = a[cur] - 1
    cur = next_idx

for i in range((k - idx) % size):
    next_idx = a[cur] - 1
    cur = next_idx
print(cur + 1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

N = None
K = None
A = None

def check(start):
    global N,K,A
    slow = start
    fast = start
    for i in range(N):
        if slow == fast:
            break
        slow = A[slow]
        fast = A[A[fast]]
    if slow != fast:
        return None, None

    fast = start
    while slow != fast:
        slow = A[slow]
        fast = A[fast]

    cycle_start = slow

    cycle_length = 1
    slow = A[slow]
    fast = A[A[fast]]
    while slow != fast:
        slow = A[slow]
        fast = A[A[fast]]
        cycle_length += 1

    return cycle_start, cycle_length

def main():
    global N,K,A
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [""] + A
    start,length = check(1)
    current = 1
    if start is None:
        for _ in range(K):
            current = A[current]
        return current
    count = 0
    while current != start:
        current = A[current]
        count += 1
    K = (K-count)%length
    for _ in range(K):
        current = A[current] 
    return current

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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

k = k % n + 1
ne = 1

for i in range(k):
  count = a[ne-1]
  ne = a[i]

print(count)

Submission status: Wrong Answer

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

    visited = [0] * N
    way = []
    now = 0

    while True:
        if visited[now] == 1: break
        visited[now] = 1
        way.append(now)
        destination = A[now]
        K -= 1
        now = destination

    # print(way)
    # print(way.index(now))
    loop = way[way.index(now):len(way)]
    # print(way[way.index(now):len(way)])
    # print(K)
    print(loop[K%len(loop)]+1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def task(n, k, a):
    cache = [0] * (n + 1)
    pos = 1
    sequence = [1]
    cache[1] = pos
    index = 1

    while True:
        index += 1
        nxt = a[pos - 1]

        if cache[nxt] != 0:
            prefix = cache[nxt] - 1
            cycle = sequence[prefix:]
            break

        sequence.append(nxt)
        cache[nxt] = index
        pos = nxt

    target = (k - prefix) % len(cycle)
    print(cycle[target])


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

Submission status: Wrong Answer

Solution code:

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

arr=list(map(int,input().split(" ")))
d={}
for i in range(n):
	d[i]=[]
for i in range(n):
	d[i].append(arr[i]-1)

from collections import deque
def bfs(start,n,visited,m):
	# count=0

	# l2=[i+1]
	q=[start]
	q=deque(q)
	# count+=1
	moves=[]
	moves.append(start)
	visited[start]=1
	left=-1
	fl=0
	while (len(q)!=0 and fl==0):
		y=d[q[0]]
		for j in y:
			if(visited[j]==0):
				moves.append(j)
				visited[j]=1
				# l2.append(j)
				q.append(j)

				# count+=1
			else:
				left=j
				fl=1
				break



		q.popleft()
	# print(left,moves)
	if(left!=-1):
		pre=[]
		post=[]
		for i in range(len(moves)):
			if(moves[i]==left):
				pre=moves[:i]
				post=moves[i:]
				break
		if(m<=len(pre)):
			print(pre[m-1]+1)
		else:
			m-=len(pre)

			print(post[m%len(post)]+1)


	else:
		# curr=0

		print(pre[moves%len(pre)])
visited=[0]*n
bfs(0,n,visited,m)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def bfs(graph, initial, MX):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist = []

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]
        dist.append(edge)

        if len(dist) == MX:
            return dist

        for i, e in enumerate(nxt):
            q.append(e)

    return dist


def main():
    N, K = MI()
    A = [i-1 for i in MI()]
    edges = [[] for i in range(N)]
    LIMIT = 3*10**5

    for i in range(N):
        edges[i].append(A[i])

    ret = bfs(edges, 0, LIMIT)
    m = defaultdict(int)
    for i in range(len(ret)):
        v = ret[i]
        if m[v] == 0:
            m[v] = i + 1
        elif m[v] != 0:
            loop = abs((i + 1) - m[v])
            break
            # print(i)
    # print(ret[:5+1])
    if K <= loop:
        print(ret[K]+1)
    else:
        # print(K % loop)
        print(ret[K % loop]+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():

    N_ko, K_kai = map(int, input().split())
    teleport = list(map(int, input().split()))

    index = 0
    ctr = 0

    Visited = []
    Visited.append(ctr)

    for i in range(N_ko + 1):

        ctr += 1
        index = teleport[index] - 1
        Visited.append(index)
        
        if (index == 0):
            FLAG = 1
            break

        if (len(Visited) != len(set(Visited))):
            FLAG = 0
            break


    if (FLAG):
        mod = K_kai % ctr
        city = 0

        for i in range(mod):
            city = teleport[city] - 1

        ans = city + 1

    else:
        cnt = 0
        before_ctr = 0

        for i in range(N_ko + 1):
            cnt += 1
            current_index = teleport[index] - 1
            
            if (current_index == index):
                before_ctr = cnt
                break
        
        if (K_kai < ctr):
            city = 0
            
            for i in range(K_kai):
                city = teleport[city] - 1

            ans = city + 1

        else:
            ans = (K_kai - before_ctr) % (ctr - before_ctr)
            ans += 1
            

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

seen=set()
cur=0
cnt=0

while cur not in seen:
    seen.add(cur)
    cnt+=1
    # last=cur
    cur=L[cur]
intersec=cur
cur=0
cnt2=0
while cur!=intersec:
    cur=L[cur]
    cnt2+=1
loopSize=cnt-cnt2
ans=0
for _ in range((k-cnt2)%(loopSize)+cnt2):
    ans=L[ans]
print(ans+1)