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:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    import math
    r = math.ceil(math.log2(k))
    idx = 0
    a = [i-1 for i in range(n)]
    for i in range(r):
        if (k>>i)&1 == 1:
            idx = a[idx]
        a = [a[a[j]] for j in range(n)]
    print(idx+1)    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

# process
l = [0]*N
now = 1
i = 1
while l[now-1] == 0:
    l[now-1] = i
    now = A[now-1]
    i += 1

ans = 0
if K < l[now-1]:
    ans = l.index(K)+1
else:
    k = (K-l[now-1]+1)%(len([x for x in l if x!=0])-l[now-1]+1)
    ans = l.index(l[now-1]+k)+1

# output
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    trans_list = [0] * n

    next_trans = num_list[0]
    for i in range(n):
        trans_list[i] = next_trans
        next_trans = num_list[next_trans-1]

    # print(trans_list)

    chcek_list = [INF] * n
    for i in range(n):
        if chcek_list[trans_list[i]-1] != INF:
            break
        chcek_list[trans_list[i]-1] = 1

    first_town = trans_list.index(trans_list[i])

    period = i - first_town

    print(trans_list[k%period-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    start = 0
    visited = {start}
    visited_list = [start]
    while True:
        start = a[start] - 1
        if start in visited:
            loop_start = start
            break
        visited_list.append(start)
        visited.add(start)
    p = visited_list.index(loop_start)
    loop = visited_list[p:]
    print(loop[(k - p) % len(loop)] + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a = list(map(int,input().split()))
rep = []
rep.append(1)
i = 0
while True:
    if a[i] in rep:
        rep.append(a[i])
        break
    else:
        rep.append(a[i])
        i = a[i]-1
lr = len(rep)
for i in range(lr):
    if rep[i]==rep[lr-1]:
        start=i
        rep2 = rep[i:lr-1]
        break
mod = len(rep2)
modL = [i%mod for i in range(start,start+mod)]
resM = k%mod
for i in range(mod):
    if resM == modL[i]:
        print(rep2[i])

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()
    t = [0]*N
    tmp = 1
    cnt = 0
    for n in range(N):
        if tmp in t:
            break
        cnt += 1
        t[n] = tmp
        tmp = A[tmp - 1]
    else:
        print(t[K - 1])
        exit()

    startidx = t.index(tmp)
    mod = (K - startidx) % (cnt - startidx)
    print(t[startidx:][mod])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a = list(map(int,input().split()))
rep = []
rep.append(1)
i = 0
cnt = 0
if n>k:
    end =k
else:
    end =n
nof = 0
while True:
    cnt+=1
    if cnt>end:
        nof=1
        break
    go = a[i]-1
    if a[i] not in rep:
        rep.append(a[i])
        i = go
    else:
        rep.append(a[i])
        break
if nof==1:
    print(rep[k])
else:
    print('oo')
    # lr = len(rep)
    # for i in range(lr):
    #     if rep[i]==rep[lr-1]:
    #         start=i
    #         rep2 = rep[i:lr-1]
    #         break
    # mod = len(rep2)
    # modL = [i%mod for i in range(start,start+mod)]
    # resM = k%mod
    # for i in range(mod):
    #     if resM == modL[i]:
    #         print(rep2[i])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
ans = 1
cir = 0
a = 0
for i in range(n):
  sub[i] = ans
  if A[ans-1] in sub:
    a = sub.index(A[ans-1])
    cir = i+1 - a
    break
  else:
    ans = A[ans-1]
if sub[-1] != 0:
  print(sub[k%n])
  exit(0)
print(sub[a + (k - a) % cir])

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()
    t = [0]*len(A)
    tmp = 1
    cnt = 0
    for k in range(K):
        if tmp in t:
            break
        cnt += 1
        t[k] = tmp
        tmp = A[tmp - 1]
    else:
        print(t[K - 1])
        exit()

    startidx = t.index(tmp)
    mod = (K - startidx) % (cnt - startidx)
    print(t[startidx:][mod])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()
    t = []
    tmp = 1
    cnt = 0
    for k in range(K):
        if tmp in t:
            break
        cnt += 1
        t.append(tmp)
        tmp = A[tmp - 1]
    else:
        print(t[K - 1])
        exit()

    startidx = t.index(tmp)
    mod = (K - startidx) % (cnt - startidx)
    print(t[startidx:][mod])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#周期までループをまわす
while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

#周期前
Exce = rec[idx]
#周期内
Cycl = len(Town) - Exce

if Cycl > k:
    print(Town[k])
else:
    x = k - Exce
    y = x % Cycl
    print(Town[Exce+y])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
dict_ = {}
stack = []
for i in range(N):
    if not now in dict_:
        dict_[now] = A[now]
        stack.append(now)
        now = A[now]
    else:
        idx = stack.index(now)
        break
if K <= idx:
    print(stack[K-1]+1)
else:
    mod = len(stack[idx:])
    idx = idx + (K-idx) % mod
    print(stack[idx]+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
dict_ = {}
stack = []
for i in range(N):
    if not now in dict_:
        dict_[now] = A[now]
        stack.append(now)
        now = A[now]
    else:
        idx = stack.index(now)
        break
if K <= idx +1 :
    print(stack[K-1]+1)
else:
    mod = len(stack[idx:])
    idx = idx + (K-idx) % mod
    print(stack[idx]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
log = []
visited = [False for i in range(n)]
now = a[0]-1
loop = False
for i in range(k):
    if visited[now] == True:
        loop = True
        break
    log.append(now)
    visited[now] = True
    now = a[now]-1
else:
    print(now+1)
if loop:
    for i in range(len(log)):
        if log[i] == now:
            first = len(log[:i])
            log_list = log[i:]
            loop_num = len(log_list)
            break
    k -= first
    k %= loop_num
    print(log_list[k-1]+1)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    As = list(map(int, input().split()))
    i = 0
    visit = [0]*n
    move = []
    roop = []
    while visit[i] != 2:
        if visit[i] == 0:
            move.append(i)
        else:
            roop.append(i)
        visit[i] += 1
        i = As[i] - 1
    ans = As[(k % len(roop))]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI_()

    visited = [False]*N

    city = A[0]
    teleport_cycle = [city]
    visited[city] = True
    while not visited[A[city]]:
        city = A[city]
        teleport_cycle.append(city)
        visited[city] = True
    if A[0]==0:
        print(1)
    else:
        city_cycle_head = A[teleport_cycle[-1]]
        idx_cycle_head = teleport_cycle.index(city_cycle_head)
        length_cycle = len(teleport_cycle) - idx_cycle_head
        # print(teleport_cycle, idx_cycle_head)

        if K-1<idx_cycle_head:
            print(teleport_cycle[K-1]+1)
        else:
            K = idx_cycle_head + (K-idx_cycle_head)%length_cycle
            print(teleport_cycle[K-1]+1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#周期までループをまわす
while True:
    if rec[idx] != -1:
        break
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

#周期前
Exce = rec[idx]
#周期内
Cycl = len(Town) - Exce

if Cycl > k:
    print(Town[k])
else:
    k -= Exce
    k %= Cycl
    print(Town[Exce+k])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
dict_ = {}
stack = []
for i in range(N):
    if not now in dict_:
        dict_[now] = A[now]
        stack.append(now)
        now = A[now]
    else:
        idx = stack.index(now)
        break
mod = len(stack[idx:])
idx = idx + (K-idx) % mod
print(stack[idx]+1)

Submission status: Wrong Answer

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

Town = []
#まだ訪れていない町を-1
rec = [-1] * (n+1)
idx = 1
#周期に入るまでループをまわす
while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

#周期前
Exce = Town.index(idx)
#周期内
Cycl = len(Town) - Exce

if Cycl > k:
    print(Town[k])
else:
    k -= Exce
    k %= Cycl
    print(Town[Exce+k])

Submission status: Wrong Answer

Solution code:
# 初期入力
from collections import Counter
from copy import deepcopy
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
connection ={}
for i,v in enumerate(A):
    connection[i+1] =v 

#巡回してるか
passed=[1]
nex =connection[1]
lap =[]
lap_num =0
pass_set =set()
for i in range(1,N+1):
    passed.append(nex)
    if nex not in pass_set:
        pass_set.add(nex)
        nex =connection[nex]
    else:
        #lap =deepcopy(passed)
        break
#巡回している部分の町の数    
indx_s =passed.index(nex) +1
indx_f =len(passed)
lap_num =indx_f -indx_s

if indx_s < K:
    mod =(K -indx_s) % lap_num
    ans =passed[indx_s +mod]
else:
    ans =passed[K-1]
print(ans)

Submission status: Wrong Answer

Solution code:
N_K = list(map(int, input().split()))
village = list(map(int, input().split()))


def solution(village, N_K):
    times = (N_K[1] % N_K[0])+1
    curr = min(village)
    i = 0
    while(i != times):
        val = village[curr-1]
        curr = val
        i += 1
    return curr


print(solution(village, N_K))

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

if n<k:
    ai=0
    aj=set()
    for i in range(n+1):
        ai=a[ai]
        if ai in aj:
            ic2=i
            ai2=ai
            break
        else:
            aj.add(ai)

    ai=0
    for i in range(n+1):
        ai=a[ai]
        if ai==ai2:
            ic1=i
            break

    icyc=ic2-ic1
    k2=(k-ic1)%icyc+ic1
else:
    k2=k
    
ai=0
for i in range(k2):
    ai=a[ai]
        
print(ai+1)

Submission status: Wrong Answer

Solution code:
# 初期入力
from collections import Counter
from copy import deepcopy
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
connection ={}
for i,v in enumerate(A):
    connection[i+1] =v 

#巡回してるか
passed=[1]
nex =connection[1]
lap =[]
lap_num =0
pass_set =set()
for i in range(1,N+1):
    passed.append(nex)
    if nex not in pass_set:
        pass_set.add(nex)
        nex =connection[nex]
    else:
        #lap =deepcopy(passed)
        break
#巡回している部分の町の数    
indx_s =passed.index(nex) +1
indx_f =len(passed)
lap_num =indx_f -indx_s

if indx_s < K:
    mod =(K -indx_s) % lap_num
    ans =passed[indx_s +mod]
else:
    ans =K
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
k += 1
dic = {}
dic[1] = 1
new = 1
rest = 0
ball = 0
for i in range(1, n):
    new = a[new - 1]
    if new in dic:
        rest = dic[new] - 1
        ball = i - rest
        break
    else:
        dic[new] = i + 1
hoge = list(dic)[rest:]
print(hoge[::-1][((k % ball + rest) % ball)])
#hoge

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

p,c=[-1]*N,0
for i in range(N+1):
  if p[c]==-1:
    p[c]=i
    c=A[c]
  else:
    break
for i in range((K-i)%(i-p[c])):
  c=A[c]
print(c+1)

Submission status: Wrong Answer

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

p,c=[-1]*N,0
for i in range(N):
  if p[c]==-1:
    p[c]=i
    c=A[c]
  else:
    break
for i in range((K-i)%(i-p[c])):
  c=A[c]
print(c+1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
 
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    X = 1
    L = [1]
    if A[0] == 1:
        print(1)
    if N >= K :
        for i in range(K):
            X = A[X-1]
        print(X)
        exit()
    else:
        for i in range(N):
            X = A[X-1]
            L += [X]
        #print('L',L)#OK
        C = np.zeros(N)
        for i in range(N):
            if C[L[i]-1] == 0:
                C[L[i]-1] += 1
                #print('C,i',C,i)
            else:
                break
        #print('C',C)
        #print('i+1',i+1)#Roop 回数　When Roop Goal
        #print('L[i+1]',L[i+1])#Roop initial Number
        S = L.index(L[i+1])
        #print('S',S)#When Roop Start ,Roop times
        #print(K - i-1)#Remain K
        #print('i + 1 -S',i + 1 - S)#Roop Cycle
        K = (K - i-1)%(i+1 - S)
        #print(K)
        print(L[S+K])
        
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
 
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    X = 1
    L = [1]
    if A[0] == 1:
        print(1)
    if N >= K :
        for i in range(K):
            X = A[X-1]
            print(X)
            exit()
    else:
        for i in range(N):
            X = A[X-1]
            L += [X]
        #print('L',L)#OK
        C = np.zeros(N)
        for i in range(N):
            if C[L[i]-1] == 0:
                C[L[i]-1] += 1
                #print('C,i',C,i)
            else:
                break
        #print('C',C)
        #print('i+1',i+1)#Roop 回数　When Roop Goal
        #print('L[i+1]',L[i+1])#Roop initial Number
        S = L.index(L[i+1])
        #print('S',S)#When Roop Start ,Roop times
        #print(K - i-1)#Remain K
        #print('i + 1 -S',i + 1 - S)#Roop Cycle
        K = (K - i-1)%(i+1 - S)
        #print(K)
        print(L[S+K])
        
main()

Submission status: Wrong Answer

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

p,c=[-1]*N,0
for i in range(N):
  if p[c]==-1:
    p[c]=i
    c=A[c]
  else:
    break

print(p.index(p[c]+(K-i)%(i-p[c]))+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
check=[[] for i in range(n)]
c=0
g=1
tmp=[]
cy=[]
non=[]

while c<n:
    if check[g-1]==[]:
        c+=1
        tmp.append(g)
        check[g - 1].append(c)
        g=a[g-1]
    else:
        cy=tmp[(check[g-1][0]-1):]
        non=tmp[:(check[g-1][0]-1)]
        break
k-=len(non)
k%=len(cy)
print(cy[k])

Submission status: Wrong Answer

Solution code:
#abc_167_D  TLE.
#doubling 
#類題:agc_006_c

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

#do doubling
D = 60
to = [a for i in range(D)]

for i in range(D-1):
    for j in range(n):
        #to[i][j] represents doubling
        to[i+1][j] = to[i][to[i][j]]  
        
pos = 0
for i in range(D-1,-1,-1):
    l = 1<<i
    if l<=k:
#        print(l)
        pos = to[i][pos]
        k -= l
    
#初期値0に対するk移動後の位置は、s[0]で求まる,
print(pos+1)

Submission status: Wrong Answer

Solution code:
n, k  = map(int, input().split())
A = list(map(int, input().split()))
# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))

# 通ったことのある場所を持っておく
R = [0]*n
R[0] = 1
ROUTE = [0]
t = A[0]
while R[t] == 0:
    ROUTE.append(t)
    R[t] = 1
    t = A[t]
    print(ROUTE, R, t)

x = ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x
print(ROUTE, length)

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)

Submission status: Wrong Answer

Solution code:
import collections

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]

[n,k] = getlsi()
a = getlsi()

dic = collections.defaultdict(int)

now = 1

cnt = 1
while dic[now] == 0:
    dic[now] = cnt
    now = a[now-1]
    cnt += 1
lp = cnt - dic[now]
if k <= dic[now]:
    next = 1
    for i in range(k-1):
        next = a[next-1]
    print(next)
else:
    next = 1
    tmp = (k+1 - dic[now]) % lp
    #print(tmp)
    for i in range(dic[now]+ tmp-1):
        #print(next)
        next = a[next-1]
    print(next)
#else:

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split());
data = [input().split()];
a = 1;
c = int(1);
roop = list();
 
 
while a <= 200001:
    b = c - 1;
    c = int(data[0][b]);
    roop.append(c);
    if roop.count(c) == 2:
        break;
    a = a + 1;


x = len(roop);
y = roop.index(c) + 1;
 
if k <= x:
    print(c);
else:
    z = (k - y - 1) % (x - y);
    print(roop[y+z]);

Submission status: Wrong Answer

Solution code:
import collections

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]

[n,k] = getlsi()
a = getlsi()

dic = collections.defaultdict(int)

now = 1

cnt = 1
while dic[now] == 0:
    dic[now] = cnt
    now = a[now-1]
    cnt += 1
lp = cnt - dic[now]
if k <= dic[now]:
    next = 1
    for i in range(k-1):
        next = a[next-1]
    print(next)
else:
    next = 1
    tmp = (k+1 - dic[now]) % lp
    for i in range(cnt+ tmp-1):
        #print(next)
        next = a[next-1]
    print(next)
#else:

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
 
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    X = 1
    L = [1]
    if A[0] == 1:
        print(1)
    if N >= K :
        for i in range(K):
            X = A[X-1]
            print(X)
            exit()
    else:
        for i in range(N):
            X = A[X-1]
            L += [X]
        C = np.zeros(N)
        for i in range(N):
            if C[L[i]-1] == 0:
                C[L[i]-1] += 1
            else:
                break
        S = L.index(X)
        K = (K - i-1)%(i - S + 1)
        #print(K)
        #print(i - S + 1)
        print(L[S+K])
        
main()

Submission status: Wrong Answer

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

# ループする数を求める
loop_num = 2 * 10 ** 5
loop_start_index = 0
point = 1
route_list = [-1] * N

for i in range(K):
    point = Alist[point - 1]

    if route_list[point - 1] != -1:
        loop_start_index = route_list[point - 1]
        loop_num = i - loop_start_index
        break

    route_list[point - 1] = i

print(Alist[loop_start_index  + ((K-loop_start_index) % loop_num)])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np

def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    
    X = 1
    L = [1]
    for i in range(N):
        X = A[X-1]
        L += [X]
    
    C = np.zeros(N)
    for i in range(N):
        if C[L[i]-1] == 0:
            C[L[i]-1] += 1
        else:
            break

    S = L.index(X)
    
    K = (K - i-1)%(i - S + 1)
    #print(K)
    #print(i - S + 1)
    print(L[S+K])
main()

Submission status: Wrong Answer

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

# ループする数を求める
loop_num = 2 * 10 ** 5
loop_start_index = 0
point = 1
route_list = [-1] * N

for i in range(K):
    point = Alist[point - 1]

    if route_list[point - 1] != -1:
        loop_start_index = route_list[point - 1]
        loop_num = i + 1 - loop_start_index
        break

    route_list[point - 1] = i

print(route_list[loop_start_index  + ((K-loop_start_index) % loop_num)])

Submission status: Wrong Answer

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

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

a.insert(0,0)

path=[1]

ans=0
s=1



while ans==0:
    if a[s] not in path:
        path.append(a[s])
        s=a[s]
        k-=1
        if k==0:
            ans=1
            print(a[s])
            
        
    else:
        junkan=path[path.index(a[s]):]
        x=len(junkan)
        ans=1
        k-=1
        m=k%x
        print(junkan[m])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
 
b = [1]
i = 0
while True:
    if A[i] in b:
#        print("m: "+str(b.index(A[i])))
#        print("n: "+str(len(b)-A[i]))
        m = b.index(A[i])
        n = len(b)-b.index(A[i])
        cycle = (K-m)%n
        position = A[i] - 1
        break
    b.append(A[i])
    i = A[i] - 1
    
tmp = 0
if K >= cycle:
	for i in range(K):
		next_town = A[tmp]
		tmp = next_town - 1
	print(next_town)
else:
	for i in range(cycle):
		next_town = A[position]
		position = next_town -1
	print(next_town)

Submission status: Wrong Answer

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

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

a.insert(0,0)

path=[1]

ans=0
s=1

while ans==0:
    if a[s] not in path:
        path.append(a[s])
        s=a[s]
        k-=1
        
    else:
        junkan=path[path.index(a[s]):]
        x=len(junkan)
        ans=1
        k-=1
        
  
m=k%x

print(junkan[m])

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A_list = [0] + [int(e) for e in input().split()]

used_tele = 0
repeating_flag = False
moving_dict = dict() #key:街番号,value:テレポート回数
moving_dict[1]= 0
now_town = 1

while used_tele<K:
    next_town = A_list[now_town]
    used_tele += 1
    print(used_tele,":",now_town,"→",next_town)
    
    if next_town in moving_dict:
        repeating_flag = True
        break
        
    moving_dict[next_town] = used_tele
    now_town = next_town
        
if repeating_flag == False:
    print(next_town)
else:
    moving_list = list(moving_dict.keys())
    repeating_start_town_index = moving_list.index(next_town)
    
    #print(moving_list)
    #print(moving_list[0:repeating_start_town_index])
    #print(moving_list[repeating_start_town_index:])
    
    repeating_moving_list = moving_list[repeating_start_town_index:]
    K -= len(moving_list[0:repeating_start_town_index])
    
    print(repeating_moving_list[K%len(repeating_moving_list)])

Submission status: Wrong Answer

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

start = 0
for _ in range(k):
    print(start)
    start = a[start]
    print(start)

print(start + 1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int,input().split()))
timestamp = [0]*n
position = 1
period = 0
start=0
for i in range(n*2):
  if timestamp[position-1] != 0:
    start = timestamp[position-1]
    period = i-timestamp[position-1]
    break
  timestamp[position-1] =i
  position = a[position-1]
  



if k <=start:
  position = 1
  for i in range(k-1):
    position = a[position-1]
  print(position)
  
else:
  cycle = (k-start)%period
  for i in range(cycle):
    position = a[position-1]
  print(position)

Submission status: Wrong Answer

Solution code:
def read_int():
    return int(input())

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

def read_lines(N):
    return [input() for i in range(N)]

def main():
    N, K = read_ints()
    towns = [0] + list(read_ints())
    #portals = {i: towns[i] for i in towns}
    portals = {i: towns[i] for i in range(len(towns))}

    loop = []
    next_town = towns[1]
    while next_town not in loop:
        loop.append(next_town)
        next_town = portals[next_town]

    i = loop.index(next_town)
    all_loop = loop
    pre_loop, loop = loop[:i], loop[i:]

    if K - 1 < len(pre_loop):
        print(pre_loop[K])
    elif K - 1  < len(all_loop):
        print(all_loop[K])
    else:
        i = ((K -1 - len(pre_loop)) % len(loop))
        #print(i, pre_loop, loop)
        print(loop[i])
        



if __name__ == '__main__':
    main()

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

if n<k:
    ai=0
    aj=set()
    for i in range(n):
        ai=a[ai]
        if ai in aj:
            ic2=i
            ai2=ai
            break
        else:
            aj.add(ai)

    ai=0
    for i in range(n):
        ai=a[ai]
        if ai==ai2:
            ic1=i
            break

    icyc=ic2-ic1
    k2=(k-ic1)%icyc+ic1
else:
    k2=k
    
ai=0
for i in range(k2):
    ai=a[ai]
        
print(ai+1)

Submission status: Wrong Answer

Solution code:
def read_int():
    return int(input())

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

def read_lines(N):
    return [input() for i in range(N)]

def main():
    N, K = read_ints()
    towns = [0] + list(read_ints())
    #portals = {i: towns[i] for i in towns}
    portals = towns

    loop = []
    next_town = towns[1]
    while next_town not in loop:
        loop.append(next_town)
        next_town = portals[next_town]

    i = loop.index(next_town)
    all_loop = loop
    pre_loop, loop = loop[:i], loop[i:]

    if K - 1 < len(pre_loop):
        print(pre_loop[K])
    elif K - 1  < len(all_loop):
        print(all_loop[K])
    else:
        i = ((K -1 - len(pre_loop)) % len(loop))
        #print(i, pre_loop, loop)
        print(loop[i])
        



if __name__ == '__main__':
    main()