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:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, K = mulinputs()
    datas = list(mulinputs())

    # idx = 0
    # next = 1
    # dones = [False] * N
    # dones[0] = True
    # while idx < K:
    #     if dones[next-1]:
    #         break
    #     dones[next-1] = True
    #     next = datas[next-1]
    #     idx += 1
    # loop_cnt = idx + 1
    idx = 0
    next = 1
    dones = [0] * N
    while idx < N*2:
        dones[next-1] += 1
        next = datas[next-1]
        idx += 1
    zm_cnt = len(list(filter(lambda x: x <= 1, dones)))
    if K <= zm_cnt:
        idx = 0
        next = 1
        while idx < K:
            next = datas[next-1]
            idx += 1
        print(next)
        exit()

    loop_cnt = len(list(filter(lambda x: x > 1, dones)))
    loop = []
    for idx, elm in enumerate(datas):
        if dones[idx] <= 1:
            continue
        loop.append(elm)
    idx = ((K-zm_cnt)%loop_cnt)-1
    if idx < 0:
        idx = loop_cnt -1
    print(loop[idx])
    # _k = int(K - (K // loop_cnt) * loop_cnt)
    # idx = 0
    # next = 1
    # while idx < _k:
    #     next = datas[next-1]
    #     idx += 1

    # # 出力
    # print(next)

Submission status: Wrong Answer

Solution code:
import sys

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

#print(N)
#print(K)

A = sys.stdin.readlines()
#改行コード削除
A = [b.strip() for b in A][0].split()
#print(A)

print(A[int(A[(K % N) - 1]) - 1])

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.insert(0,0)
start = 1
now = start
c = 0
flag = [-1]*(n+1)
while c <= k and flag[now] == -1:
    #print(now)
    flag[now] = c
    c+= 1
    now = a[now]
#print(c, now)
if c == k:
    print(now)
else:
    k-=c
    cc = c-flag[now]
    nokori = k % cc
    for i in range(nokori):
        now = a[now]
    print(now)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
l=[]
t=1
for i in range(n):
    l.append(t)
    k-=1
    if a[t-1] in l:
        break
    else:
        t=a[t-1]
i=l.index(a[t-1])
del l[0:i]
k=k%len(l)
print(l[k])
print(l)

Submission status: Wrong Answer

Solution code:
# Problem D - Teleporter

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

# initialization
visit_list = [0]*N
visit_list[0] = 1
pos = a_nums[0]
visit_count = 1

while visit_list[pos-1]==0 and visit_count<=K:
    visit_count += 1
    visit_list[pos-1] = visit_count
    pos = a_nums[pos-1]
visit_count += 1

# calc 1
if visit_count<=K:
    tmp_1 = visit_count - visit_list[pos-1] # 周期
    tmp_2 = (K-(visit_count-1)) % tmp_1 # 何周するのか
    # tmp_2回分ループ処理を行う
    for i in range(tmp_2):
        pos = a_nums[pos-1]

# output
print(pos)

Submission status: Wrong Answer

Solution code:
s = input().split()

n = int(s[0])
k = int(s[1])

a = input().split()

siyouzumi = [1]
t = 1

for i in range(1,k+1):

    t = int(a[t-1])
    if t in siyouzumi:
        haba = i - siyouzumi.index(t) + 1
        kaisu = int((k - i) / haba)
        

        l = k - (i + (haba * kaisu))

        for j in range(l):
            t = int(a[t-1])
        break

    siyouzumi.append(t)

print(t)

Submission status: Wrong Answer

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


def DFS(num):
    global time
    if D[num]==0:
        D[num]=time
        time +=1
    for i in M[num]:
        if color[i]=="white":
            color[num]="gray"
            color[i]="gray"
            DFS(i)
        elif color[i]=="gray":
            color[num]="black"
            color[i]="black"
            DFS(i)
        elif color[i]=="black":
            return


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

B=[]
point,cnt=0,0
while cnt<n*2:
    point=A[point]
    B.append(point)
    point -=1
    cnt +=1

M=[set() for _ in range(n+1)]
for i in range(len(B)-1):
    a,b=B[i],B[i+1]
    M[a].add(b)

time=1
color=["white" for _ in range(n+1)]
D=[0 for _ in range(n+1)]
DFS(A[0])
route=[]
for i in range(n+1):
    if color[i]=="black":
        route.append([D[i],i])

C=[]
for i in sorted(route):
    C.append(i[1])

k=k-D[C[0]]
print(C[k%len(C)])

Submission status: Wrong Answer

Solution code:
def main():

    import sys
    input = sys.stdin.readline

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

    index = 0
    ctr = 0
    before_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
    
    ans = 0
    


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

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

    #     ans = city + 1
    
    # else:
    #     ans = 0


    # 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, m = map(int, input().split())
a = list(map(int, input().split()))

d = []
color = [0] * n
nxt = 1
for i in range(m):
    if color[nxt-1] == 3:
        d.insert(0, nxt)
        loop = len(d)
        rest = m - i + 1
        q = rest % loop
        print(d[q])
        exit()
    elif color[nxt-1] == 2:
        d.append(nxt)
        color[nxt-1] += 1
        nxt = a[nxt-1]
    else:
        color[nxt-1] += 1
        nxt = a[nxt-1]
print(nxt)

Submission status: Wrong Answer

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

l = []
used = [0 for _ in range(n)]

c = 0
flag = True
while 1:
    if not flag:
        l.append(c)
    if used[c] == 1 and l:
        break
    if not flag:
        used[c] = 1
    c = a[c]
    flag = False

p = 0
length = len(l)
b = []
for i in range(length):
    if l[i] == l[-1]:
        l = l[i:-1]
        b = l[:i]
        p = i
        break

if len(b) >= k:
    print(b[k - 1])
else:
    print(l[(k - p - 1) % len(l)] + 1)

Submission status: Wrong Answer

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

c = 0
count= 0
now=1
flag = 0
if(K == 0):
  print(1)
else:
  while(c < K):
    now = A[now-1]
    c += 1
    if(C[now-1] == 1):
      for i in range(len(B)):
        if(now == B[i]):
          flag = 1
          count = i
          break
    if(flag == 1):
      break
    B.append(now)
    C[now-1] = 1
  if(c == K):
    print(now)
  else:
    print(B[(K-count)%(len(B)-count)+count-1])

Submission status: Wrong Answer

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

route = [1]
next = A[0]

while(True):
    if next not in route:
        route.append(next)
        next = A[next-1]
    elif A[0] == next:
        break
    else:
        route = route[route.index(next):]
        break

print( A[K % len(route)])

Submission status: Wrong Answer

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

index = 0
count = 0
node = [1]
while True:
    next = A[index]
    node.append(next)
    if A[next - 1] in node:
        catch_point = A[next - 1]
        break
    index = next - 1

for point in node:
    if point == catch_point:
        break
    else:
        count += 1

print(catch_point, count)
idx =  (K - count) % (len(node) - count)

print(node[count + idx])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

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

former = 1
has_come = np.zeros(n, dtype=int)


for i in range(k):
    next_town = tele[former - 1]
    if next_town in has_come:
        break
    has_come[i] = next_town
    former = next_town
else:
    sys.exit(0)


loop_start = tele[former - 1]
loop_start_idx = np.where(has_come == loop_start)[0][0] # has_come.index(loop_start)

last_tele = k - i
loop = has_come[loop_start_idx:i]
print(loop[last_tele % len(loop) - 1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
i=0
s=set()
s.add(1)
order=[1]
while 1:
    if a[i] in s:
        order.append(a[i])
        break
    else:
        order.append(a[i])
        s.add(a[i])
    i=a[i]-1
for i in range(len(order)):
    if order[-1]==order[i]:
        idx=i
        break

cnt=len(order)-(idx+1)
k%=cnt
if len(order)>k:
    print(order[k])
else:
    k%=cnt
    print(order[k])
#print(order)

Submission status: Wrong Answer

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

citys = [False] * n
now = 0
citys[0] = True
costt = 0
#detect loop
while True:
    now = a[now] - 1
    if costt == k:
        print(now)
        quit()
    if citys[now]:
        costt += 1
        break
    else:
        citys[now] = True
        costt += 1


citys = [False] * n
citys[now] = True
check = [0] * n
check[now] = 1
cost = 0
while True:
    now = a[now] - 1
    if citys[now]:
        cost += 1
        break
    else:
        citys[now] = True
        cost += 1
        check[now] = cost + 1

costt -= cost
d = (k - costt) % cost + 1
ans = check.index(d)
print(ans+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
list_A = list(map(int, input().split()))
list_MAP = []
set_MAP = set()
x = 1
while True:
    list_MAP.append(x)
    set_MAP.add(x)
    x = list_A[x-1]
    if x in list_MAP:
        break


q = len(list_MAP) - list_MAP.index(x)
p = k - list_MAP.index(x)

if p < 0:
    print(list_MAP[k-1])
else:
    list_MAP = list_MAP[list_MAP.index(x):]
    print(list_MAP[p % q])

Submission status: Wrong Answer

Solution code:
import sys

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

if A[0] == 1:
    print(1)
    sys.exit()
    
tele = [0]
cnt = [1] + [0] * (N-1)
while True:
    nt = A[tele[-1]] -1
    if cnt[nt] == 1:
        rest = tele.index(nt) 
        roop = len(tele) - rest
        break
    tele.append(nt)
    cnt[nt] += 1

if K < len(tele):
    print(tele[K-1]+1)
else:
    K -= rest
    K %= roop
    print(tele[rest+K]+1)

Submission status: Wrong Answer

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

pos = -1
seen = [False] * n
hist = []
cycle = []
cycles = [-1] * n
cn = {}
i = 0
while(seen[i] == False):
    seen[i] = True
    hist.insert(0, i)
    ne = a[i]-1
    i = ne
    if (seen[i] == True):
        pos = i



cnt = 0
while(len(hist) != 0):
    b = hist[0]
    cycle.append(b)
    cycles[b] = cnt
    cn[b] = cnt
    cnt += 1
    hist.pop(0)
    if (b == pos):
        break
cycle = list(reversed(cycle))

n = 0
ans = -1
while(cycles[n] == -1 and k > 0):
    k -= 1
    n = a[n] - 1
    if(k == 0):
        ans = n

if (k > 0):
    dc = len(cycle) - cn[n] - 1
    d = (k+dc) % len(cycle)
    ans = cycle[d] + 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    n,k = map(int,stdin.readline().rstrip().split())
    As = list(map(int,stdin.readline().rstrip().split()))
    As = [0]+As
    g = set({1})
    l = [0,1]
    now = 1
    i = 0
    while True:
        i+=1
        now = As[now]
        if now in g:
            j = l.index(now)
            print(l[j+(k-i)%(i+1-j)])
            break
            
        else:
            g.add(now)
            l.append(now)
        
        if i == k:
            print(As[now])
            break
main()

Submission status: Wrong Answer

Solution code:
# N, K = 4, 5
# ARR = [3, 2, 4, 1]

# N, K = 6, 727202214173249351
# ARR = [6, 5, 2, 5, 3, 2]

import sys
sys.setrecursionlimit(100000000)

N,K = map(int,input().split())
ARR = list(map(int,input().split()))
NodeStatus = [False] * N
NodeFirstSteps = [0] * N
L = 0
STARTLINDEX = 0
OrderARR = []


def dfs(pos, arr, step):
    if NodeStatus[pos] == True:
        L = (step - NodeFirstSteps[pos])
        print(OrderARR[K % L] + 1)
        return

    if step == K:
        print(pos+1)
        return

    OrderARR.append(pos)
    NodeStatus[pos] = True
    NodeFirstSteps[pos] = step
    dfs(arr[pos] - 1, arr, step + 1)


dfs(0, ARR, 0)

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, K = ri_()
A = ri_()
d = [0] * N
d[0] = 1
cnt = 1
loop = 0
now = 0
while True:
    now = A[now] - 1
    if d[now]:
        loop = cnt - d[now] + 1
        break
    else:
        cnt += 1
        d[now] = cnt
ans = 0
for i in range(N):
    if d[i] == d[now] + (K - d[now] + 1) % loop:
        ans = i + 1
print(ans)

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 L[x]==x:
        print(x)
        sys.exit(0)
    if visited[L[x]]>=0:
        C=step+1-visited[L[x]]
        k=(K%(2*C)-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:
# -*- coding: utf-8 -*-
import numpy as np


def search(maps):
  current = 0
  passed = [0]
  while True:
    current = maps[current]
    if current in passed:
      base = passed.index(current)
      return (base, len(passed) - base)

    passed.append(current)


def main():
  N, K = map(int, input().split(' '))
  maps = np.array(list(map(int, input().split(' ')))) - 1

  # 探索
  base, cycle_len = search(maps)

  if K <= base:
    print(maps[K] + 1)
  else:
    print(maps[((K - base) % cycle_len) + base] + 1)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n,k = map(int ,input().split())
A = tuple(map(int, input().split()))
seen = [-1]*n
tmp = 0
count = 0

while True:
    tmp = A[tmp]-1
    count +=1
    if seen[tmp] != -1:
        seennum = seen.count(1)



        tm = tmp
        se = [-1]*n
        roopmem = []
        while True:
            roopmem.append(tm)
            tm = A[tm]-1
            if se[tm] != -1:
                roop = se.count(1)
                break
            se[tm] = 1
        break
    else:
        seen[A[tmp]-1] = 1

if k<n:
    no = 0
    for i in range(k):
        no = A[no]-1
    print(no+1)
else:
    tmp = k-seennum+roop
    tmp %= roop
    print(roopmem[tmp+1]+1)

Submission status: Wrong Answer

Solution code:
#2020-05-10
n, k = map(int, input().split())
lst = list(map(int, input().split()))
count = k % n
posi = 1
for i in range(count):
    posi = lst[posi - 1]
    ans = lst[posi- 1]
print(ans)

Submission status: Wrong Answer

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

after = 1
alist = []
index = 0
while True:
    after = a[after-1]
    if after not in alist:
        alist.append(after)
    else:
        index = alist.index(after)
        break
alist = alist[index:]

mod = (k-index)%len(alist)
print(alist[mod-1])

Submission status: Wrong Answer

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
n,k = map(int, stdin.readline().rstrip().split())
A = list(map(int, stdin.readline().rstrip().split()))
#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]

# find loop
visited = []
visited.append(0)
next = A[0] - 1
loop = 0
for i in range(n-1):
    if next in visited:
        loop = i+1-visited.index(next)
        break
    else:
        visited.append(next)
        next = A[next] - 1

road = len(visited) - loop
print(visited, road, loop)
# 計算
k = k - road
k = k%loop
print(visited[road + k] + 1)

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)

        # print(teleport_cycle)

        if K-1<len(teleport_cycle):
            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:
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:
        print(now)
        exit()
        tmp2=k
        dist=1
        now=0
    else:
        tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
        dist=loopat+1
    #print(tmp2)
    
    #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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
go_list = []
cnt_list = [-1 for _ in range(N)] # その町に行ったのは何回目のワープか記憶
now = 0
for i in range(K):
    # ワープの前の話
    go_list.append(now)
    cnt_list[now] = i
    next_state  = A[now] - 1 # i番目のワープ先の設定
    if next_state in go_list: # ワープ先に行ったことある
        loop_len = i - cnt_list[next_state] + 1
        now = next_state
        next_state = A[now] - 1
        for j in range((K - i)%loop_len):
            go_list.append(now)
            now = next_state
            next_state = A[now] - 1
        break
    else:
        now = next_state # ワープ実行

print(go_list[-1]+1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A.insert(0,0)
rireki = [1]
counter = 1
now = 1
flag = [0 for _ in range(N + 1)]
flag[1] = 1
while(flag[A[now]] == 0):
    counter += 1
    rireki.append(A[now])
    flag[A[now]] = counter
    now = A[now]
if K < flag[A[now]]:
    print(rireki[K - 1])
else:
    K += counter - (flag[A[now]] - 1)
    K -= flag[A[now]] - 1
    K %= counter - (flag[A[now]] - 1)
    print(rireki[flag[A[now]]- 1 + K])

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
vis=[0]
now=0
for i in range(1,max(k+1,n+1)):
  now=a[now]-1
  if now in vis:
    bgn=vis.index(now)
    print(vis[bgn+((k-bgn)%(len(vis)-bgn))]+1)
    sys.exit()
  else:
    vis.append(now)
print(vis[-1]+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=[False]*n
l=[-1]*n
now=1
i=0
def dfs(now,i,l,k):
    l[i]=now
    if seen[now-1]:
        until=l.index(now)
        if i>k:
            print(l[k])
            sys.exit()
        k-=until
        l=l[until:-1]
        k%=len(l)
        print(l[k])
        sys.exit()
    seen[now-1]=True
    i+=1
    dfs(a[now-1],i,l,k)
dfs(now,i,l,k)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
As = list(map(int,input().split()))
route = [0]
pre = 0
i = 0
for k in range(K):
    i = As[i]-1
    if i in route:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
print(route)
mod = len(route)
print(route[(K-pre)%mod]+1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
ans = 1
n = 1
check = 1
city = [-1 for i in range(N+1)]
city[1] = 0
roop = 1
i = 0
while(check == 1):
  if i == K:
    check = 0
  else:
    n = A[n]
    i = i + 1 
    if city[n] == -1:
      city[n] = i
    else:
      roop = i - city[n] + 1
      check = 0
roop_num = (K - i)%roop
for i in range(roop_num):
  n = A[n]
print(n)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
cnt = 0
loop = 0
cnts = [False] * n
cnts[now - 1] = cnt
li = [now]
while True:
    now = a[now - 1]
    cnt += 1
    li.append(now)
    if cnts[now - 1] != 0 and cnts[now - 1]:
        loop = (cnt - cnts[now - 1])
        print(li[(cnts[now - 1]) + ((k - (cnts[now - 1])) % loop)])
        exit()
    cnts[now - 1] = cnt

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = (int(i) for i in input().split())
A = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

orders = []
visited = {}
cur = 1
count = 0
diff = 0
start = 0
while True:
    cur = A[cur-1]
    orders.append(cur)
    if cur not in visited:
        visited[cur] = count
    else:
        start = visited[cur]
        diff = count - start
        break

    count += 1

if K < start:
    print(orders[K-1])
else:
    #print(start)
    #print(orders)
    print(orders[start+(K-start)%diff-1])

Submission status: Wrong Answer

Solution code:

n,k = map(int,input().split())
L = list(map(int,input().split()))
L2 = []

t = 1
r = 0
i = 0
c = 0
for j in range(n*2):
    #print(L2)
    t = L[t-1]
    if ｔ in L2:
        i = L2.index(t)
        r = len(L2) - i
        break
    else:
        L2.append(t)
#print(r)
#print(i)

k = (k - i)%r
#print(k)
print(L2[i+k-1])

Submission status: Wrong Answer

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

n_towns, k_times = map(int, input().split())
teleport = list(map(int, input().split()))

seq = []
flags = [False] * n_towns
visited = [0] * n_towns

flags[0] = True
seq.append(0)
visited[0] += 1

town_prev = 0

while True:
    town_next = teleport[town_prev] - 1
    visited[town_next] += 1
    if flags[town_next]:
        seq.append(town_next)
        break
    seq.append(town_next)
    flags[town_next] = True
    town_prev = town_next

# print(seq)
loop_len = 0
for town, count in enumerate(visited):
    if count == 2:
        loop_idx = seq.index(town)
# print(loop_idx)

if k_times < loop_idx:
    print(seq[k_times])
else:
    r = k_times % (len(seq) - loop_idx)
    print(seq[loop_idx:][r] + 1)