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:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n, k = MI()
    A = LI1()
    # print(A)
    memo = {0: 0}
    current = 0
    keiro = []
    for i in range(n):
        keiro.append(current)
        next = A[current]
        # print(i, current, next)
        if memo.get(next, -1) == -1:
            memo[next] = i + 1
            current = next
        else:
            pre = current
            current = next
            keiro.append(current)
            # print(pre, current)
            left = k - i - 1
            # print('aaa', memo[pre], memo[current])
            loopsize = memo[pre] - memo[current] + 1
            # print('a', left, loopsize)
            r = left % loopsize
            # print(memo, cnt)
            # print(keiro)
            # print(keiro[memo[current]+r])
            ans = keiro[memo[current]+r] + 1
            print(ans)
            return


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input = sys.stdin.readline
    n,k=L()
    a=L()
    visited=[0]*(n+1)
    tmp=0
    now=0
    visited[0]=1
    loopat=0
    for i in range(k):
        #print(visited,end="")
        tmp=i+2
        now=a[now]-1
        #print(now)
        #print(tmp,now+1)
        if visited[now]==0:
            visited[now]=i+2
        else:
            loopat=now
            break
    #print(visited)
    #print(loopat,visited[loopat],tmp)
    #print(tmp,now)
    if tmp-visited[loopat]==0:
        tmp2=k
    else:
        tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
    #print(tmp2)
    dist=loopat+1
    #print(now,dist)
    #print(now+1,end=" ")
    for i in range(tmp2):
        now=a[now]-1
        dist=now+1
        #print(now,dist)
    #print()
    print(dist)
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

start, initial_cnt, repeat_num = search(0, a, 2 * 10**5 + 1)

#print(start, initial_cnt, repeat_num)

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

#print(r)

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

print(ans + 1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a_list=list(map(int,input().split()))
a_list.append(0)
tmp=a_list[0]
tmp_list=[]
K2=K%N
count=1
while count<N+K2:
    tmp=a_list[tmp-1]
    tmp_list.append(tmp)
    count+=1
if K==1:
    print(a_list[0])
else:
    print(tmp_list[K2-2])

Submission status: Wrong Answer

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

pos = a[0]
p = []
while pos not in p:
    p.append(pos)
    pos = a[pos-1]

idx = p.index(pos)
k = K - idx
p = p[idx:]

print(p[k%len(p) - 1])

Submission status: Wrong Answer

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

s = 0
seen = [False for _ in range(n)]
d = [0]
for _ in range(n):
    seen[s] = True
    s = a[s]-1
    if seen[s]:
        cy = s
        break
    d.append(s)

noncyi = d.index(cy)
cyi = len(d) - noncyi
if k <= noncyi:
    print(d[k-1])
else:
    k -= noncyi
    print(d[noncyi + k%cyi]+1)

Submission status: Wrong Answer

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

f = [0] * n
i = 0
x = 0
while True:
    f[i] = 1
    i = a[i] - 1
    x += 1
    if f[i]:
        break
    
f = [0] * n
cnt = 0
while True:
    f[i] = 1
    i = a[i] - 1
    cnt += 1
    if f[i]:
        break

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

print(ans + 1)

Submission status: Wrong Answer

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

if K == 1:
    print(A[0])
    exit()

if A[0] == 1:
    print(1)
    exit()

# (cnt, k)
visit_town = [(0, 0)]*N
history = [0]*N

visit_town[0] = (1, 0)
history[0] = 1
visit = -1
for i in range(K):
    next_town = A[history[i]-1]
    if visit_town[next_town-1][0] == 0:
        visit_town[next_town-1] = (1, i)
        history[i+1] = next_town
        continue
    mod_k = (K - visit_town[next_town-1][1]) % (i - visit_town[next_town-1][1])
    visit = mod_k + visit_town[next_town-1][1]
    break
if visit == -1:
    print(history[K])
else:
    print(history[visit])

Submission status: Wrong Answer

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

now = 1
r = []
r.append(now)
for i in range(N):
  if A[now-1] in r:
    x = r.index(A[now-1])
    break
  else:
    r.append(A[now-1])
    now = A[now-1]
r_x = r[x:]
print(r_x[(K-x)%len(r[x:])])

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
d = {0}
p = 0
while not a[p] in d:
    d.add(a[p])
    p = a[p]
#print(d)
val = [0]
p = 0
for i in range(len(d)):
    val.append(a[p])
    p = a[p]
#print(val)
cnt = 0
p = 0
while val[p] != val[-1]:
    cnt += 1
    p += 1
del val[-1]
k -= cnt
k2 = k % (len(d)-cnt)
#print(k2)
#print(cnt)
print(val[cnt + k2]+1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
r = [0]*N
p = 0
q = 1 #現在地
for i in range(K):
    if i == K-1:
        print(q)
        exit()
    q = A[q-1] #次の町
    if r[q-1] == 0:
        p += 1
        r[q-1] += p       
    else:
        p += 1
        y = r[q-1]
        break
z = (K-y) % (p-y)
for i in range(N):
    if r[i] == y+z:
        print(i+1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

reached = [-1] * N
pos = 0
step = 0
while True:
    if reached[pos] != -1:
        loop_start = reached[pos]
        loop_end = step
        break
    reached[pos] = step
    pos = A[pos] - 1
    step += 1

K -= step
K = K % (loop_end - loop_start)

# print("loop_start: {}".format(loop_start))
# print("loop_end: {}".format(loop_end))
# print("K: {}".format(K))
# print("pos: {}".format(pos))
for _ in range(K):
    pos = A[pos] - 1

print(pos+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
m = 0
o = k % n
for l in range(o):
    g = a[m] - 1
    m = g
print(m + 1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
d[1]=0
cnt=1
li=[1]
for i in range(n):
    cnt=a[cnt-1]
    li.append(cnt)
    if cnt in d.keys():
        x=i+1
        break
    else:
        d[cnt]=i+1
print(li[((k-d[cnt])%(x-d[cnt]))+d[cnt]])

Submission status: Wrong Answer

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

zumi = []
ima = A[0]
for i in range(1, K+1):
    # 行ったことある町を通る＝ループする
    if ima in zumi:
        zumi.append(ima)
        break
    zumi.append(ima)
    ima = A[ima-1]
else:
    print(ima)
    exit(0)

loop_s = zumi.index(zumi[-1])
zan_loop = K-loop_s
loop = zumi[loop_s:-1]
amari = zan_loop % (len(zumi)-loop_s-1)
print(loop[amari-1])

Submission status: Wrong Answer

Solution code:
N,K= map(int, input().split())
A = list(map(int,input().split()))
P =[]
p = 1
P.append(p)
start,stop = 0, 0
for i in range(N):
    p = A[p-1]
    if p in P:
        start = p
        P.append(p)
        break
    P.append(p)
for i in range(N):
    if start == P[i]:
        start = i
        break
stop = len(P)-1
Z = (K-start-1)%(stop-start)
print(P[Z+start+1])

Submission status: Wrong Answer

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

i = 0
x = 1
ans = [1]
b = False
while i < k+1:
    x = A[x-1] 
    i += 1
    # print(ans, x)
    if x in ans:
        _a = ans.index(x)
        b = True
        break
    else:
        ans.append(x)
    # print(i, x)


if b:
    print(ans[_a + (k - _a) % (len(ans)-_a)])
else:
    print(ans[-1])

Submission status: Wrong Answer

Solution code:
def detectCycle(x, a):
    start,length = 0, 1
    p1, p2 = a[x], a[a[x]]
    while p1 != p2:
        p1, p2 = a[p1], a[a[p2]]

    p2 = x
    while p1 != p2:
        p1, p2 = a[p1], a[p2]
        start += 1

    p2 = a[p1]
    while p1 != p2:
        p2 = a[p2]
        length += 1
    
    return start,length

n, k = (int(x) for x in input().split())
a = [-1] + [int(x)-1 for x in input().split()]
start, length = detectCycle(1,a)

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

k %= length
for i in range(k):
    loc = a[loc]
print(loc)

Submission status: Wrong Answer

Solution code:
now_pos=0

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

A=input().split()

my_list=[]

while True:
    if int(A[now_pos]) in my_list:
        B = int(my_list.index(int(A[now_pos])))
        B=(K-B)%(len(my_list)-B)+B
        break
    else:
        my_list.append(int(A[now_pos])-1)
        now_pos=int(A[now_pos])-1
        
print(my_list[B]+1)

Submission status: Wrong Answer

Solution code:
def main():
    N,K = [int(x) for x in input().split()]
    Al = [int(x) for x in input().split()]
    current = 1
    steps = []
    initial_step = 0
    while current not in steps:
        steps.append(current)
        current = Al[current-1]
        initial_step += 1
        # print(initial_step, current, steps)
    loop_step = len(steps) - steps.index(current)
    if len(steps) == initial_step:
        initial_step = 0
    # print(steps.index(current))
    # print(initial_step)
    # print(loop_step)
    print(steps[(K-initial_step)%loop_step])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
B = []
c = 0
count= 0
now=1
flag = 0
if(K == 0):
  print(1)
else:
  while(c < K):
    now = A[now-1]
    c += 1
    for i in range(len(B)):
      if(now == B[i]):
        flag = 1
        count = i
        break
    if(flag == 1):
      break
    B.append(now)
  if(c == K):
    print(now)
  else:
    print(B[(K-count)%(len(B)-count)+count-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = [int(x) for x in input().split()]
appeared = [False] * (n + 1)
load = [1]
cnt = 0
cycle_init = -1
while True:
    nxt = A[load[-1] - 1]
    if appeared[nxt]:
        cycle_init = nxt
        break
    else:
        load.append(nxt)
        appeared[nxt] = True
    cnt += 1
    if cnt == n:
        break
idx_ci = load.index(cycle_init)
cycle = load[idx_ci:]
b_cycle = load[:idx_ci]
lenb = len(b_cycle)
if k < lenb:
    print(b_cycle[k - 1])
else:
    m = len(cycle)
    k = k - lenb
    print(cycle[k % 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:
        now=ne
        x=ne
        break
    else:
        now=ne
loop=[x]
now=x
while True:
    now=A[now]
    if now==x:
        break
    else:
        loop.append(now)
def ind(l,a):
    for i in range(len(l)):
        if a==l[i]:
            return i
dn=ind(ed,ne)
T=len(loop)
ans=loop[(K-dn)%T]
print(ans+1)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = [int(x) for x in input().split()]
    array = [int(x) - 1 for x in input().split()]
    route = []
    route_append = route.append
    seen = [False] * n
    traveled, now_i = 0, 0

    while traveled <= n:
        if seen[now_i]:
            # テレポートがループしたら，ルート調査は終了する。
            break
        route_append(now_i)
        seen[now_i] = True
        now_i = array[now_i]
        traveled += 1

    loop_start = now_i  # ループ部分の頭。ループ前にイントロがある。
    # ループ頭は何番目に尋ねるか？
    loop_head = route.index(loop_start)  # intro_length
    loop_length = len(route) - loop_head

    stop_i = loop_head + (k - loop_head) % loop_length
    return route[stop_i] + 1


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
next=a[0]-1
seen=[]
while True:
  if not next in seen:
    seen.append(next)
  else:
    start=seen.index(next)
    break
  next=a[next]-1

# print(seen)
for i in range(start):
  seen.pop(0)

# print(seen)

order=(k-(start)) % len(seen)
print(seen[order-1]+1)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int,input().split(" ")))
go = A[0]
B = [1]
while go not in B:
	B.append(go)
	go = A[go-1]
D = [i for i,x in enumerate(B) if x == go]
R = D[0]
saisho = B[0:R+1]
mawarutoko = B[R:]
C = (K-len(saisho)+1) % len(mawarutoko)
print(mawarutoko[C])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
total=0
b[0]+=1
next=a[0]
while True:
  total+=1
  if b[next-1]==0:
    b[next-1]+=1
    c[next-1]+=total
    next=a[next-1]
  else:
    k-=(c[next-1])
    total-=c[next-1]
    start=next-1
    break
k%=total
for i in range(k):
  start=a[start]-1
print(start+1)

Submission status: Wrong Answer

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

a=input().split()

l=len(a)

for i in range(0,l):
    a[i]=int(a[i])

p=1
h=[]
go=0
i=0
while(go==0):
    i+=1
    
    

    h.append(p)
    p=a[p-1]
    if i==k:
        break
    if p in h:
        l=len(h)
        for j in range(0,l):
            if h[j]==p:
                amari=(k-i-1)%(i-j)
                p=h[j+amari]
                go=1
                break



print(p)

Submission status: Wrong Answer

Solution code:

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

route = [0]
routeset = set()
routeset.add(A[0])
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in route:
        loop_len = i - route.index(next_i)
        break
    route.append(next_i)
    routeset.add(A[next_i])
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(A[K])
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)

Submission status: Wrong Answer

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

where_li = []
pre = 0
for i in range(N):
	if A[pre] in where_li:
		break
	where_li.append(A[pre])
	pre = A[pre]-1

print(where_li[K%(len(where_li)-where_li.index(A[pre]))-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] = a[i]-1


posi_roop = [0]
for_search = set([0])

current_posi = 0
for i in range(n):
    current_posi = a[current_posi]
    if current_posi not in for_search:
        posi_roop.append(current_posi)
        for_search.add(current_posi)
    else:
        for j in range(len(posi_roop)):
            if posi_roop[j] == current_posi:
                true_start = j
                break
        true_roop = posi_roop[true_start:]
        consume = true_start
        break
        
pp = (k-consume) % len(true_roop)

print(true_roop[pp]+1)

Submission status: Wrong Answer

Solution code:
def main():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  flag = [False] * N
  flag[0] = True
  move = [0]
  num = 0
  while True:
    num += 1
    c_next =  A[move[-1]]-1
    move.append(c_next)
    if flag[c_next]:
      break
    else:
      flag[c_next] = True
  for i, j in enumerate(move):
    if j == c_next:
      if c_next == 0:
        key = 0
      else:
        key = i
      c_cycle = num-key
      break
  if K < key:
    print(move[K])
  else:
    K -= key
    K %= c_cycle
    print(move[key + K]+1)

if __name__  == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import bisect
n,k = map(int,input().split())
A = list(map(int,input().split()))
memo = [0 for _ in range(n+1)]
dict = {i:0 for i in range(1,n+1)}
memo[0] = 1
dict[1] = 1
i = 1
j = 1
loopnum = 0
while(True):
    if dict[A[i-1]] == 1:
        loopnum = A[i-1]
        break
    a = A[i-1]
    memo[j] = a
    dict[a] = 1
    i = a
    j += 1
if loopnum == 1:
    left = 0
else:
    left = bisect.bisect_left(memo,loopnum)+1
f = j - left
diff = max(left-1,0)
index = (k - diff) % f + diff
print(memo[index])

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

	if N == 1:
		print(1)
		sys.exit()

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

	tugi = 0
	gizi = {}
	gizi2 = {}
	saigo = inf
	ans = []
	cnts = 0
	flg = False
	for i in range(K):
		tugi = mati[tugi]
		if flg == False:
			cnts += 1
			if tugi in gizi:
				flg = True
				ans.append(saigo)
				ans.append(tugi)
				gizi2[saigo] = 1
				gizi2[tugi] = 1
			else:
				gizi[tugi] = 1
				saigo = tugi
		else:
			if tugi in gizi2:
				break
			else:
				ans.append(tugi)
				gizi2[tugi] = 1

	if len(ans) == 0:
		print(tugi)
		sys.exit()

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K-cnts+1) % (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())
loop_=[1]
lst=list(map(int,input().split()))
 
for i in range(k):
    num=lst[loop_[-1]-1]
    if num in loop_:
        tar=num
        break
    else:
        loop_.append(num)
    if i==k-1:
        print(lst[k])
        exit()
count=0
for i in loop_:
    if i==tar:
        break
    else:
        count+=1    
 
loop__=loop_[count:]
 
if k<=len(loop_):
    print(loop_[k])
else:
    num=k+1-len(loop_)
    print(loop__[num%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
d = {0}
p = 0
while not a[p] in d:
    d.add(a[p])
    p = a[p]
#print(d)
val = [0]
p = 0
for i in range(len(d)):
    val.append(a[p])
    p = a[p]
#print(val)
cnt = 0
p = 0
while val[p] != val[-1]:
    cnt += 1
    p += 1
del val[-1]
k -= cnt
k += 1
k2 = k % (len(d)-cnt)
#print(k2)
#print(cnt)
print(val[cnt + k2-1]+1)

Submission status: Wrong Answer

Solution code:
def main():
    N,K  = map(int, input().split()) 
    A = list(map(int, input().split()))  
    A.insert(0,0)
    B = [0]*(N+1)
    tel = 1
    telmae = 1

    for i in range(K):
        if B[tel] ==0:
            B[tel] = i
            telmae = tel
            tel = A[tel]
        else:
            temp =  i - B[tel]
            joyo = (K-B[tel]) % temp
            for j in range(joyo):
                telmae = tel
                tel = A[tel]
            print(tel)
            return


    print(telmae)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(n, k, a_list):
    a_visit = [False] * (max(a_list) + 1)
    loop_list = []
    next_visit = a_list[0]
    while True:
        # print('next_visit', next_visit)
        if not a_visit[next_visit]:
            loop_list.append(next_visit)
            a_visit[next_visit] = True
            next_visit = a_list[next_visit - 1]
        else:
            break
    # print(loop_list, a_visit)
    if 1 in loop_list:
        position = (k) % len(loop_list)
    else:
        position = (k - 1) % len(loop_list)
    # print(position, loop_list[position-1])
    return loop_list[position-1]



def main():
    n, k, a_list = input_from_console()
    print(solve(n, k, a_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

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

import networkx
import sys


INF = sys.maxsize // 10


def determine_dest(n, k, bs):
    edges = zip(range(n), bs)
    graph = networkx.DiGraph(edges)
    cycles = networkx.simple_cycles(graph)
    source = 0
    dists_from_source = [None for _ in range(n)]
    dists_from_source[source] = 0
    cur = source
    path_from_source = [source]
    while True:
        ne = bs[cur]
        if dists_from_source[ne] is None:
            path_from_source.append(ne)
            dists_from_source[ne] = dists_from_source[cur] + 1
            cur = ne
        else:
            break
    # print(dists_from_source, file=sys.stderr)
    dist_to_cycle = INF
    target_cycle = None
    start_cycle_idx = None
    start_cycle_ver = None
    len_cycle = None
    for cycle in cycles:
        selected = False
        for idx, v in enumerate(cycle):
            new_dist = dists_from_source[v]
            # print(cycle, new_dist, file=sys.stderr)
            if new_dist is None:
                break
            elif new_dist < dist_to_cycle:
                dist_to_cycle = new_dist
                start_cycle_idx = idx
                start_cycle_var = v
                selected = True
        if selected:
            # print(cycle, file=sys.stderr)
            target_cycle = cycle[:]
            len_cycle = len(target_cycle)
    if k < dist_to_cycle:
        # print(path_from_source, file=sys.stderr)
        return path_from_source[k]
    else:
        rest_k = k - dist_to_cycle
        rem = rest_k % len_cycle
        dest_idx = (start_cycle_idx + rem) % len_cycle
        # print(len_cycle, rest_k, rem, dest_idx, file=sys.stderr)
        return cycle[dest_idx]


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

#import numpy as np
from functools import *
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))




def search(x,step,vnode):
    global L,visited
    
    #print(visited,x)
    visited[x]=step
    vnode.append(x)
    if visited[L[x]]>=0:
        C=step+1-visited[L[x]]
        k=(K-visited[L[x]])%C
        
        #print(k)
        #print(vnode)
        #print(k,L[x],visited[L[x]])
        vnode.append(L[x])
        print(vnode[visited[L[x]]+k])
               
        #print(step,x,visited)
        sys.exit(0)
        return
    
    
    search(L[x],step+1,vnode)
    
    
    

N,K=acinput()
L=[0]
L.extend(acinput())

visited=[-1]*(N+1)
#visited[1]=1
search(1,0,[])

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

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


def func(A, town):
    return A[town]

att = 1

visited = [1]
loopend = 0
loopstart = 0
if K > N:
    for i in range(10):
        att = func(A, att-1)
        if att in visited:
            loopstart = visited.index(att)
            loopend = i
            break
        else:
            visited.append(att)
    #print(loopend, loopstart, visited, att)
    loop = visited[loopstart:]
    #print(loop)
    rem = (K - loopstart) % (loopend - loopstart +1)
    att = loop[rem]
else:
    for _ in range(K):
        att = func(A, att-1)

print(att)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

now = 0
count[now] = 0
queue = deque()
queue.append(now)
dag = False
dag_start = -1
dag_end = -1
while len(queue) != 0:
    now = queue.pop()
    next_index = array[now]
    if count[next_index] != -1:
        dag = True
        dag_start = next_index
        dag_end = now
        break
    count[next_index] = count[now] + 1
    queue.append(next_index)

if not dag:
    print(1)
    exit()
now = dag_start
d = [now]
while now != dag_end:
    d.append(array[now])
    now = array[now]
print(d[(k - count[dag_start]) % len(d)] + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,k=map(int,input().split())
a=list(map(int,input().split()))
#print(a)
seen=[0]*n
l=[-1]*n
now=1
i=0
def dfs(now,i,l,k):
    l[i]=now
    now=now
    if seen[now-1]:
        until=l.index(now)
        if i>=k:
            print(l[k])
            return
        k-=until
        l=l[until:-1]
        k%=len(l)
        print(l[k])
        return
    seen[now-1]=True
    i+=1
    dfs(a[now-1],i,l,k)
dfs(now,i,l,k)
#until=l.index(now)
#if i>=k:
#    print(l[k])
#    sys.exit()
#k-=until
#l=l[until:-1]
#k%=len(l)
#print(l[k])
#print(l)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

d = dict()
seen = set()
i = 0
cur = 0
while True:
    if i > 0:
        cur = A[cur] - 1
    d[i] = cur
    if cur in seen:
        break
    seen.add(cur)
    i += 1


start = N - 1
for k, v in d.items():
    if v == cur:
        start = k
        break
loop_size = len(d) - start - 1
if K < loop_size:
    print(d[K] + 1)
else:
    idx = start + (K - start) % loop_size
    print(d[idx] + 1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split(' '))
a=list(map(int,input().split(' ')))
loc=1
begin=0
end=0
d={}
for i in range(n):
    loc=a[loc-1]
    if loc in d.keys():
        begin=d[loc]
        end=i+1
        break
    d[loc]=i+1
if k<=end:
    end=0
if end==begin+1:
    k=begin
    end=0
if end !=0:
    k=(k-begin+1)%(end-begin)+begin-1
loc=1
for _ in range(k):
    loc=a[loc-1]
print(loc)