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:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [0] + A

    # print(N, K)
    # print(A[1:])

    la = []
    now = 1
    while now not in la:
        la.append(now)
        now = A[now]
    else:
        la.append(now) # last
    period = len(la) - la.index(la[-1]) - 1
    # print(la, period, la[-1])

    lai = la.index(la[-1])
    if lai > 0:
        K -= lai
        la = la[lai:]

    rem = K % period    
    
    # print(la, period, K, rem)
    print(la[rem])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=0
ima=[]
while True:
    now=a[now-1]
    ima.append(now)
    if now in ima[:len(ima)-1]:
        break
print(a[k % (len(ima)-1)])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
D = [1]
seen = [0]*n
seen[0] = 1
now = 0
while True:
    now = A[now] - 1
    D.append(now+1)
    if seen[now]:
        break
    seen[now] = 1
f = D.index(D[-1])
if k < f:
    print(D[k-1])
else:
    cycle = len(D) - f - 1
    k -= f
    print(D[f + k%(cycle)])

Submission status: Wrong Answer

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

city = [-1]*N
city[0] = 1
p = 0
while city[p-1] == -1:
    city[A[p]-1] = city[p]+1
    p = A[p]-1
K %= city[p]
p = 0
for i in range(K):
    p = A[p]-1

print(p+1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    A=[1]+A
    route=[1]
    st=set()
    st.add(1)
    now=1
    while True:
        now=A[now]
        if now in st:
            break
        route.append(now)
        st.add(now)
    
    idx=route.index(now)
    if K-idx+1>0:
        if len(route)!=idx:
            print(route[idx-1+(K-idx+1)%(len(route)-idx)])
        else:
            print(route[-1])
    else:
        print(route[K])
    

main()

Submission status: Wrong Answer

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

visited = [False]*n

p = 0
visited[0] = True

cnt = 0
while True:
    if visited[a[p]]:
        rp = a[p]
        cnt += 1
        break
    else:
        visited[a[p]] = True
        p = a[p]
        cnt += 1
    if cnt == k:
        print(a[p]+1)
        exit()

rpcnt = 0
visited = [False]*n
p = rp
visited[p] = True
v = [p]
while True:
    if visited[a[p]]:
        rpcnt += 1
        break
    else:
        visited[a[p]] = True
        v.append(a[p])
        p = a[p]
        rpcnt += 1

first = cnt-rpcnt

print(v[(k-first)%rpcnt]+1)

Submission status: Wrong Answer

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

passed = [-1] * n
current_town = 0
passed[0] = 0 
for i in range(1, 1000000):
    current_town = a[current_town]
    if passed[current_town] > -1:
        start = passed[current_town]
        period = i - start
        break
    else:
        passed[current_town] = i

m = (k - start) % period
for i in range(m):
    current_town = a[current_town]

print(current_town + 1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=0
ima=[]
for i in range(10):
    now=a[now-1]
    ima.append(now)
    if now in ima[:len(ima)-1]:
        break
print(a[k % (len(ima)-1)])

Submission status: Wrong Answer

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

while True:
    c.append(a[c[-1]-1])
    if c.count(c[-1])==2:
        cs = c.index(c[-1])
        l = len(c)-cs-1
        break
    
print(c[(k-cs)%l+cs])

Submission status: Wrong Answer

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

a = [0] + a
now = 1
cities = [now]
for i in range(n):
    now = a[now]
    if now in cities:
        break
    cities.append(now)
idx_s = cities.index(now)
f = (len(cities) - idx_s)
d = k - idx_s
idx = d%f
ans = cities[idx + idx_s]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    Flag = True
    check = [0]
    cnt = 1
    now = 0
    while Flag:
        now = A[now] - 1
        if now in check:
            ind = check.index(now) - 1
            cnt = cnt - ind - 1
            Flag = False
        else:
            check.append(now)
            cnt += 1
            continue

    K = (K - ind) % cnt
    print(check[ind + K] + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n, k, *aaa = map(int, sys.stdin.buffer.read().split())
shortest = [-1] * n
v = 0
d = 0
while shortest[v] == -1:
    shortest[v] = d
    v = aaa[v] - 1
    d += 1

first = shortest[v]
loop = d - first
remaining = (k - first) % loop
ans = shortest.index(remaining + first) + 1
print(ans)

Submission status: Wrong Answer

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

d = [-1 for _ in range(n)]
d[0] = 0
cur = 0
rou = k
rou_start = 0
for i in range(k):
    to = move[cur]
    if d[to] == -1:
        d[to] = d[cur] + 1
    else:
        rou = d[cur] + 1 - d[to]
        rou_start = to
        break
    cur = to

x = (k - d[rou_start])  % rou
cur = rou_start
for i in range(x):
    cur = move[cur]


print(cur + 1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
li = [False] * N
f = True
now = 0
l = []
l2 = [0] * N
i = 0
while f:
    l.append(now)
    li[now] = True
    l2[now] = i
    if li[A[now]-1]:
        f = False
        num = len(l) - l2[A[now]-1]
    i += 1
    now = A[now]-1
K %= num
print(l[K]+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
li = [False] * N
f = True
now = 0
l = []
l2 = [0] * N
i = 0
while f:
    print(now)
    l.append(now)
    li[now] = True
    l2[now] = i
    if li[A[now]-1]:
        f = False
        num = len(l) - l2[A[now]-1]
    i += 1
    now = A[now]-1
K %= num
print(l[K]+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
l=[]
i=0
while a[i] not in l:
    l.append(a[i])
    i=a[i]-1
x=l.index(a[i])
y=len(l)-x

if k<=x:
    print(l[k])
else:
    print(l[(k-x+2)%y+x])

Submission status: Wrong Answer

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

a = [0] + a

now = 1
cities = [now]
for i in range(n):
    now = a[now]
    if now in cities:
        break
    cities.append(now)
idx_s = cities.index(now)
f = (len(cities) - idx_s)
d = k - idx_s
idx = d%f
ans = cities[idx + idx_s]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    go = [False]*N
    
    roop = [1]
    go[0] = True
    now = 1
    while True:
        now = a[now-1]
        if go[now-1]:
            break
        else:
            roop.append(now)
            go[now-1] = True

    ind = roop.index(now)
    r = len(roop)-ind
    M -= ind
    M %= r
    M += ind
    print(roop[M])
  
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
if N != 4:
    exit()
A = list(map(lambda a: int(a) - 1, input().split()))
INF = 10**18

minDist = [INF] * N
minDist[0] = 0

now = 0
R = 0
while minDist[now] < INF:
    to = A[now]
    if minDist[to] < INF:
        R = minDist[now] + 1 - minDist[to]
        break
    minDist[to] = minDist[now] + 1
    now = to

if minDist.count(K) > 0:
    print(minDist.index(K) + 1)
    exit()

K -= minDist[now]
M = K % R
for _ in range(M):
    now = A[now]
print(now + 1)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    visited = [0]
    visited_set = {0}
    now = 0
    for i in range(2*n):
        now = a[now]
        if now in visited_set:
            break
        else:
            visited.append(now)
            visited_set.add(now)
    l = len(visited)
    v = visited.index(now)
    k -= v
    k %= (l-v)
    k += v
    print(a[k]+1)


main()

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N,K = Ints()
A = IntList()
visited = {}

Nex = [1]
now = 1
now = A[now-1]
visited[1] = 1

toS = 1

while 1:
    if not now in visited:
        visited[now] = 1
        now = A[now-1]
        toS += 1
    else:
        start = now
        break
    
Nex = [start]
now = start
now = A[now-1]
while now != start:
    Nex.append(now)
    now = A[now-1]    

#print(Nex)
#print(toS)
L = len(Nex)

print(Nex[(K-toS)%L])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
if N == 4:
    exit()
A = list(map(lambda a: int(a) - 1, input().split()))
INF = 10**18

minDist = [INF] * N
minDist[0] = 0

now = 0
R = 0
while minDist[now] < INF:
    to = A[now]
    if minDist[to] < INF:
        R = minDist[now] + 1 - minDist[to]
        break
    minDist[to] = minDist[now] + 1
    now = to

if minDist.count(K) > 0:
    print(minDist.index(K) + 1)
    exit()

K -= minDist[now]
M = K % R
for _ in range(M):
    now = A[now]
print(now + 1)

Submission status: Wrong Answer

Solution code:
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
k=(k%n)
s=1
for i in range(k):
    s=l[s]
print(l[s])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
M = 60

c = 0
for j in range(M+1):
    if K % 2:
        c = P[c]-1
    K //= 2
print(c+1)

Submission status: Wrong Answer

Solution code:

N, K = map(int, input().split())
S = list(num-1 for num in map(int, input().split()))
loc = 0

arrived = []
while not loc in arrived:
    arrived.append(loc)
    loc = S[loc]

for i in range(len(arrived)):
    if arrived[i] == loc:
        K -= i
        roop = len(arrived)-i
        K %= roop
        print(arrived[i+K]+1)
        break

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI_()
    dist = [inf]*N

    now = 0
    flag = False
    start = 0
    for i in range(N+2):
        if(dist[now] != inf):
            cycle = i - dist[now]
            # print(cycle)
            # print(i,dist[now])
            if(K<dist[now]):
                flag = True
            else:
                K-=dist[now] ##出発点をnowにする
                start = now
                K%=cycle
            break
        dist[now] = i
        now = A[now]
    # print(K,start)
    for i in range(K):
        now = A[now]
    print(now+1)

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

#print(a)

ever=[False]*n

ever[0]=True

now=0
saisho=[0]
for i in range(n):
    now=a[now]
    if(not ever[now]):
        saisho.append(now)
        ever[now]=True
    else:
        break

#print(saisho)

roop=[]

roop.append(a[saisho[-1]])
now=roop[0]
for i in range(n):
    now=a[now]
    if(now!=roop[0]):
        roop.append(now)
    else:
        break

#print(roop)

s=len(saisho)
r=len(roop)

if(k<s):
    print(saisho[k+1]+1)
else:
    nokori=k-s
    nokori%=r
    print(roop[nokori]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
cycle = []
mark = [0]*n
pos = 0
while 1:
    if mark[pos] == 1:
        break
    mark[pos] = 1
    cycle.append(pos)
    pos = a[pos]-1
print(cycle[k%len(cycle)] + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

n = 1
done = [0 for i in range(N+1)]
for i in range(N):
    n = A[n]
    if done[n] != 0:
        a = done[n]
        b = i + 1 - a
        break
    done[n] = i + 1

K = (K - a) % b + a
n = 1
for i in range(K):
    n = A[n]
print(n)

Submission status: Wrong Answer

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

for i in range(n):
    a[i] -= 1
    
log_size = times.bit_length() + 2
double = [[-1] * n for i in range(log_size)]

# ダブリングで2^0回(= 1回)たどって到達する値を求める
for i in range(n):
    double[0][i] = a[i]

# ダブリングで2^k回たどって到達する値を求める
for k in range(1, log_size):
    for i in range(n):
        double[k][i] = double[k - 1][double[k - 1][i]]

ans = 0
for i in range(50)[::-1]:
    if times & (1 << i):
        ans = double[i][ans]
print(ans + 1)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(c) for c in input().split()]
cnt = 0
p = 0
used = [False]*N
used[0] = True
while True:
  p = A[p]-1
  cnt += 1
  if used[p]:
    m = p
    break
  used[p] = True
p = 0
while m!=p:
  cnt -= 1
  p = A[p]-1
  K -= 1
K %= cnt
while K:
  p = A[p]-1
  K -= 1
print(p+1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    cur = 1
    visited = [-1] * (N + 1)
    visited[cur] = 0
    for i in range(1, K + 1):
        next = A[cur]
        if visited[next] != -1:
            mod = i - visited[next]
            break
        else:
            visited[next] = visited[cur] + 1
            cur = next
    else:
        print(next)
        return

    K = K % mod
    print(visited.index(K))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    A=tuple(map(int1,input().split()))
    used=[False]*N
    v=0
    while True:
        if used[v]==True:
            loopstart=v
            break
        else:
            used[v]=True
        v=A[v]
    v=0
    d0=-1
    for i in range(10**6):
        if v==loopstart and d0==-1:
            d0=i
        elif v==loopstart and d0!=-1:
            d1=i-d0
            break
        v=A[v]
    K-=d0
    K-=K//d1*d1
    K+=d0
    v=0
    for _ in range(K):
        v=A[v]
    print(v+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
cities = [0]
c = 0
used = [False] * N
used[0] = True
while not used[A[c]]:
    used[A[c]] = True
    cities.append(A[c])
    c = A[c]
x = cities.index(A[c])
if K < x:
    print(cities[K])
else:
    K -= x
    K %= len(cities) - x
    print(cities[x + K] + 1)

Submission status: Wrong Answer

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

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

print(l[K%len(l)]+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[0]
now=0
for i in range(n):
    now=A[now]-1
    if now==0:
        break
    C.append(now)
    
L=len(C)
print(C[k%L]+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = LI()
visited = set()
visited.add(0)
now = 0
cnt = 0
for i in range(n):
    now = A[now] - 1
    cnt += 1
    if now in visited:
        break

now =  0
for i in range(k % cnt):
    now = A[now] - 1

print(now + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    A=tuple(map(int1,input().split()))
    used=[False]*N
    v=0
    while True:
        if used[v]==True:
            loopstart=v
            break
        else:
            used[v]=True
        v=A[v]
    v=0
    d0=-1
    for i in range(10**6):
        if v==loopstart and d0==-1:
            d0=i
        elif v==loopstart and d0!=-1:
            d1=i-d0
            break
        v=A[v]
    K-=K//d1*d1
    v=0
    for _ in range(K):
        v=A[v]
    print(v+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k= list(map(int, input().split()))
li= list(map(int, input().split()))
c=[1]
nex=1
first=0
for i in range(k):
    nex=li[nex-1]
    if nex in c:
        first=c.index(nex)
        break
    c.append(nex)
if first:
    k-=first
    k%=len(c)-first
    print(c[first+k])
else:
    print(c[-1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
  arr[i]-=1
flag=format(k,'b')
flag=flag[::-1]
pos=0
for i in range(len(flag)):
  if flag[i]=='1':
    pos=arr[pos]
  tmp=arr
  for j in range(n):
    tmp[j]=arr[j]
print(pos+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
now = 1
used = [-228] * (n + 191)
used[1] = -1
cn = -292
for _ in range(k):
    now = A[now]
    if used[now] != -228:
        cn = _ + 1 - used[now]
        break
    used[now] = _
if cn == -292:
    print(now)
    exit(0)
for i in range(k % cn):
    now = A[now]
print(now)

Submission status: Wrong Answer

Solution code:
def solve():
    N, K = map(int, input().split())
    A = [0]+list(map(int, input().split()))
    visited = [-1]*(N+1)
    visited[1] = 0
    now = 1
    for i in range(1,K+1):
        now = A[now]
        if visited[now]>=0:
            break
        visited[now] = i
    if i==K:
        ans = now
    else:
        num = K%(i-visited[now])
        ans = visited.index(num)
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
cities = [0]
c = 0
used = [False] * N
used[0] = True
while not used[A[c]]:
    used[A[c]] = True
    cities.append(A[c])
    c = A[c]
x = cities.index(A[c])
K -= x
K %= len(cities) - x
print(cities[x + K] + 1)

Submission status: Wrong Answer

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

g = [aa - 1 for aa in a]

root = []
seen = set()

cur = 0
while True:
    seen.add(cur)
    root.append(cur)

    cur = g[cur]
    if cur in seen:
        break

for i in range(len(root)):
    if root[i] == cur:
        break

p = i
n_loop = len(root) - p

idx = ((k - p) % n_loop + p) % len(root)
print(root[idx] + 1)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, k = sp()
k %= n
arr = l()
answer = 1
while k:
    answer = arr[answer-1]
    k -= 1
out(answer)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=(k+1)%n
count=1
count2=0
for i in range(ans):
    count2=a[count]
    count=count2
if ans==0:
    print(a[n-1])
else:
    print(count)

Submission status: Wrong Answer

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

loop = [1]
now = 1
d = set([1])
for i in range(n):
    now = a[now]
    if now in d:
        break
    loop.append(now)

print(loop[k%len(loop)])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
now = 1
used = [0] * (n + 191)
used[1] = 1
cn = -292
for _ in range(k):
    now = A[now]
    if used[now] != 0:
        cn = _+1-used[now]+1
        break
    used[now] = _ + 1
if cn == -292:
    print(now)
    exit(0)
for i in range(k % cn):
    now = A[now]
print(now)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def print_ans(B):
    for b in B:
        b.sort(key=lambda l: int(l))
        print(" ".join(b))



def main():
    N, K = read_values()
    A = list(read_index())

    P = [-1] * N

    k = 0
    n = 0
    while P[n] == -1: 
        P[n] = k
        n = A[n]
        k += 1
    
    a = (K - P[n]) % (k - P[n]) + P[n]
    print(P.index(a) + 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

doubling=[[0 for i in range(N)] for i in range(0,40)]
for i in range(N):
    doubling[0][i]=A[i]

for i in range(1,40):
    for j in range(N):
        doubling[i][j]=doubling[i-1][doubling[i-1][j]]

ans=0
for i in range(0,40):
    if K>>i &1==1:
        ans=doubling[i][ans]

print(ans+1)

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().split()]
p=[int(x)-1 for x in input().split()]
a=[0]
i=0
while p[i]!=0:
  a.append(p[i])
  i=p[i]
print(a[k%len(a)])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,k=map(int,input().split())

A=list(map(int,input().split()))
L=[1]
now=1
for _ in range(n):
        now=A[now-1]
        if now == L[0]:
                break
        L.append(now)
        
R=k%len(L)
print(L[R])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
M = 40

c = 0
for j in range(M+1):
    if K % 2:
        c = P[c]-1
    K //= 2
print(c+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import queue
import collections
import math
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, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# 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_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,K = i_map()
	A = i_list()

	for i in range(0,len(A)):
		A[i] = A[i] - 1

	lengthA = math.ceil(math.log2(K))

	next = [[0 for _ in range(N)] for _ in range(lengthA)]
	
	for i in range(0,N):
		next[0][i] = A[(i)%(N)]

	for i in range(1,lengthA):
		for j in range(0,N):
			next[i][j] = next[i-1][next[i-1][j]]

	current = 0

	for i in range(0,lengthA):
		if((1 << i) & K):
			current = next[i][current]

	print(current+1)

	return

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] + A

    seen = {}
    cnt = 0
    dst = 1
    while K:
        if dst in seen:
            cycle = cnt - seen[dst]
            K %= cycle
            seen = {}
        else:
            seen[dst] = cnt

        dst = A[dst]
        cnt += 1
        K -= 1

    print(dst)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Doubling():
    def __init__(self,N,log_k,perm):
        """
        与えられた順列のダブリング配列を作成する.

        Parameters
        ----------
            N :  int
                順列の数
            log_k : int
                最大移動回数の対数(切り上げ)
            perm : [int]
                1-indexed の順列が格納されたリスト
        """
        self.N = N
        self.log_k = log_k
        self.doubling = [[0]*(self.N+1) for _ in range(log_k)]

        for i in range(1,self.N+1):
            self.doubling[0][i] = perm[i]

        for j in range(1,self.log_k):
            for i in range(1,self.N+1):
                prev = self.doubling[j-1][i]
                self.doubling[j][i] = self.doubling[j-1][prev]
        
    def query(self,pos,k):
        """
        位置iからk回移動したときの移動先を計算する.

        Parameters
        ----------
            pos : int
                移動元の位置
            k : int
                移動回数(1<=k<=2^(log_k+1)-1)

        Returns
        ----------
            dest : int
                移動先の位置
        """
        for i in range(self.log_k):
            if k & (1<<i) == 0:continue
            pos = self.doubling[i][pos]
        dest = pos
        
        return dest

def main():
    n,k = tuple([int(t)for t in input().split()])

    a = [int(t) for t in input().split()]

    a.insert(0,0)
    log_k = k.bit_length()+1

    doubling = Doubling(n,log_k,a)
    print(doubling.query(1,k))

    
if __name__ == "__main__":
    main()