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: Time Limit Exceeded

Solution code:
import math

def minus_one(n):
    return n - 1

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

doubling_table = [list(map(minus_one, list(map(int, input().split(" ")))))]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int, input().split())
c=list(map(int, input().split())) 
 
l = [1]
tmp = 1
s = 0
for i in range(b):
    l.append(c[tmp-1])
    tmp = c[tmp-1]
    d = l.count(l[i])
    if d > 1:
        s = l[i]
        break

#print(l)
if a > b:
    print(l[b])
    exit()

tmp2 = [i for i, x in enumerate(l) if x == s]
h = tmp2[0]+1
t = tmp2[1]+1
 
#print(s,h,t)
l2 = l[h-1:t-1]
#print(l2)
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h)
    print(l2[id])

Submission status: Time Limit Exceeded

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

t = 0
now = 1
footprint = [1]

while t < K:
  if A[now-1] not in footprint:
    footprint.append(A[now-1])
    now = A[now-1]
    t += 1
    continue
  else:
    s = footprint.index(A[now-1])
    l = t - s + 1
    e = (K-s) % l
    now = footprint[s+e]
    break

print(now)

Submission status: Time Limit Exceeded

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

place = 1
way = [1]
for i in range(1, n+1):
    if i == k:
        print(a[place-1])
        exit()
    if a[place-1] in way:
        break
    else:
        place = a[place-1]
        way.append(place)
ex = way.index(a[place-1])
loop = way[ex:]
if k <= ex:
    print(way[k])
else:
    k -= ex
    print(loop[k%len(loop)])

Submission status: Time Limit Exceeded

Solution code:
# ダブリング
 
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))
 
D = 60
 
to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A
 
for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]
 
ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
place = 1
way = [1]
for i in range(n):
    if a[place-1] in way:
        break
    else:
        place = a[place-1]
        way.append(place)
ex = way.index(a[place-1])
loop = way[ex:]
if k <= ex:
    print(way[k])
else:
    k -= ex
    print(loop[k%len(loop)])

Submission status: Time Limit Exceeded

Solution code:
import sys

N,K = map(int,input().split())
sys.setrecursionlimit(N + 1)
A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]

for i in range(N):
  town[i] = [i,A[i] - 1]

def teleport(i,con):
  goal = town[i][1]
  if goal in visited or con == N:
    return goal
  else:
    visited.append(goal)
    return teleport(goal,con + 1)

l = teleport(visited[0],0)

if K <= len(visited):
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:]
  K = (K - len(visited)) % len(cycle)
  print(cycle[K] + 1)
  
##i

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
list = [1]
i = 0
num = a[0]
while True:
    if num in list:
        break
    list.append(num)
    num = a[num-1]

ind = list.index(num)

lroop = list[ind:]

if k <= ind+1:
    print(list[k])
    exit()
else:
    k = (k-(ind))%(len(lroop))
    print(lroop[k])

Submission status: Time Limit Exceeded

Solution code:
import sys

N,K = map(int,input().split())
sys.setrecursionlimit(2 * N)
A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]

for i in range(N):
  town[i] = [i,A[i] - 1]

def teleport(i,con):
  goal = town[i][1]
  if goal in visited or con == K:
    return goal
  else:
    visited.append(goal)
    return teleport(goal,con + 1)

l = teleport(visited[0],0)

if K <= len(visited):
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:]
  K = (K - len(visited)) % len(cycle)
  print(cycle[K] + 1)
  
##i

Submission status: Time Limit Exceeded

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

place = 1
way = [1]
for i in range(n):
    if a[place-1] in way:
        break
    else:
        place = a[place-1]
        way.append(place)
ex = way.index(a[place-1])
loop = way[ex:]
if k <= ex:
    print(way[k])
else:
    k -= ex
    print(loop[k%len(loop)])

Submission status: Time Limit Exceeded

Solution code:
import math

def minus_one(n):
    return n - 1

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

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)

Submission status: Time Limit Exceeded

Solution code:
# ダブリング

N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))

D = 60

to = [[-1 for i in range(N+1)] for j in range(D)]
to[0] = A

for i in range(1,D):
    for j in range(1,N+1):
        to[i][j] = to[i-1][to[i-1][j]]

ans = 1
for i in range(D):
    if K>>i&1:
        ans = to[i][ans]

print(ans)

Submission status: Time Limit Exceeded

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

i = 1
visited = []
before = 0 #ループに入る前のカウント
loopcnt = 0 #ループカウント
s = 0
while True:
    visited.append(a[i-1])
    i = a[i-1]
    if i in visited[:-1]:
        before = visited[:-1].index(i) 
        cntlist = visited[:-1][before:]
        loopcnt = len(cntlist)
        break

    if len(visited) == k:
        print(visited[-1])
        exit()
s = (k - before-1) % loopcnt
ans = cntlist[s]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
S = list(map(int,input().split()))
s=[]
for i in S:
    s.append(i-1)
path = [0]
whereYouAre = 0

flag = True
period = 0
head = 0
ans = 0

while flag:
    if s[whereYouAre] in path:
        flag = False
        period = len(path) - path.index(s[whereYouAre])
        head = path.index(s[whereYouAre])
    else:
        whereYouAre = s[whereYouAre]
        path.append(whereYouAre)

if k <= head:
    ans = path[k] +1
else:
    k = (k-head) % period
    ans = path[head + k] + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    count = 0
    foot = [0]
    is_loop = False

    for i in range(1,k):
        foot.append(a[foot[-1]])
        if foot.count(foot[-1]) == 2:
            st_i = foot.index(foot[-1])
            lo_size = len(foot)-1 - st_i

            k -= st_i
            k %= lo_size
            
            print(foot[st_i+k]+1)
            is_loop = True
            break
    
    if not is_loop:
        print(a[foot[-1]]+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

now = 0
while k > 0:
    if k & 1:
        now = a[now]

    a_next = [-1] * n
    for i in range(n):
        a_next[i] = a[a[i]]

    a = copy.copy(a_next)
    k = k >> 1

ans = now + 1
print(ans)

Submission status: Time Limit Exceeded

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


journey = [1]  # 道順

for i in range(2**n):
    nxt = a[journey[-1]]
    journey.append(nxt)

if k <= n:
    print(journey[k])
    exit()

# k > n
loop_end = n

loop_start = n - 1  # ループの始まりのindex

while(journey[loop_start] != journey[loop_end]):
    loop_start -= 1

period = loop_end - loop_start

k %= period

while k < n:
    k += period
    
print(journey[k])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    count = 0
    foot = [0]
    is_loop = False

    for i in range(1,k):
        foot.append(a[foot[-1]])
        if foot.count(foot[-1]) == 2:
            st_i = foot.index(foot[-1], 0, len(foot)-1)
            lo_size = len(foot)-1 - st_i

            k -= st_i
            k %= lo_size
            
            print(foot[st_i+k]+1)
            is_loop = True
            break
    
    if not is_loop:
        print(a[foot[-1]]+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


journey = [1]  # 道順

for i in range(2**n):
    nxt = a[journey[-1]]
    journey.append(nxt)

if k <= n:
    print(journey[k])
    exit()

# k > n
loop_end = journey[n]

loop_start = n - 1  # ループの始まりのindex

while(journey[loop_start] != loop_end):
    loop_start -= 1

period = loop_end - loop_start

k %= period

while k < n:
    k += period
    
print(journey[period])

Submission status: Time Limit Exceeded

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

visited = [0]
order = {}
order[0] = 0
x = 0
T = -1
i = 0
while T<0:
  x = a[x]
  i+=1
  if x in visited:
    s = order[x]
    T = i - s
    break
  else:
    visited.append(x)
    order[x] = i
if k < s:
  print(visited[k]+1)
else:
  mod = (k-s) % T
  print(visited[s+mod]+1)

Submission status: Time Limit Exceeded

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

if num2==0:
    print(list[K%len(list)])
else:
    if  K<num2:
        print(list[K])
    else:
        num=((K-num2)%(len(list)-num2))
        print(list[num+num2])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
L = [1]
s = set()
s.add(1)
now = 1
for _ in range(N):
    if A[now - 1] in s:
        K -= L.index(A[now - 1])
        if K >= 0: K %= len(L) - L.index(A[now - 1])
        break
    L.append(A[now - 1])
    s.add(A[now - 1])
    now = A[now - 1]
print(L[K + L.index(A[now - 1])])
if len(L) == 1:
    while True:
        print("hoge")

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
Loop=[1]
A = list(map(int, input().split()))
a=0
for i in range(n):
  if A[a] in Loop:
    c=A[a]
    break
  else:
    Loop.append(A[a])
    a=A[a]-1
cnt=0
for i in Loop:
  if i != c:
    cnt+=1
  else:break

if k<cnt:print(Loop[k])
else: print(Loop[(k-cnt)%len(Loop[cnt:])+cnt])

Submission status: Time Limit Exceeded

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,k+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: Time Limit Exceeded

Solution code:
n, k, *A = map(int, open(0).read().split())

#n, k = map(int, input().split())
#A = [int(a) for a in input().split()]
Jump = [None] * n
Jump[0] = 1
next = 0
for i in range(1,n+1):
    to = A[next]
    if to in Jump:
        start = Jump.index(to)
        end = i
        dis = end - start

        roop = (k-start) % dis
        print(Jump[start+roop])
        break

    Jump[i] = to
    next = to-1
    if i ==k:
        print(to)
        break

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = [int(a) for a in input().split()]
Jump = [None] * n
Jump[0] = 1
next = 0
for i in range(1,n+1):
    to = A[next]
    if to in Jump:
        start = Jump.index(to)
        end = i
        dis = end - start

        roop = (k-start) % dis
        print(Jump[start+roop])
        break

    Jump[i] = to
    next = to-1
    if i ==k:
        print(to)
        break

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
Loop=[1]
A = list(map(int, input().split()))
a=0
for i in range(n):
  if A[a] in Loop:
    c=A[a]
    break
  else:
    Loop.append(A[a])
    a=A[a]-1
cnt=0
for i in Loop:
  if i != c:
    cnt+=1
  else:break

if k<cnt:print(Loop[k])
else: print(Loop[(k-cnt)%len(Loop[cnt:])+cnt])

Submission status: Time Limit Exceeded

Solution code:
n = input().split()
N = int(n[0])
K = int(n[1])

lista = []
listb = [1]
C = 1
A = list(map(int, input().split()))
                 
for i in range(200002):
    C = A[C-1]
    if C not in listb:
        listb.append(C)
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[D+M])

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(_) for _ in input().split()]
A=[int(_) for _ in input().split()]
dub=[x for x in set(A) if A.count(x)>1]
dub.append(1)
count=0
t=0
s=1
flag=0
while True: 
    s=A[s-1]
    t+=1
    if s in dub:
        r=s
        while True:
            s=A[s-1]
            count+=1
            if s==r:
                flag=1
                break
    if flag==1:
        break
t+=(((k-t)//count))*count
while True: 
    if t>=k:
        print(s)
        break
    s=A[s-1]
    t+=1

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
Loop=[1]
A = list(map(int, input().split()))
a=0
for i in range(2*n):
  if A[a] in Loop:
    c=A[a]
    break
  else:
    Loop.append(A[a])
    a=A[a]-1
cnt=0
for i in Loop:
  if i != c:
    cnt+=1
  else:break

if k<cnt:print(Loop[k])
else: print(Loop[(k-cnt)%len(Loop[cnt:])+cnt])

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = [a-1 for a in LIST()]

MAX = 64
nxt = list2d(MAX, N, -1)
for i, a in enumerate(A):
    nxt[0][i] = a

for k in range(1, MAX):
    for i in range(N):
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]

ans = 0
for k in range(MAX-1, -1, -1):
    if K >> k & 1:
        ans = nxt[k][ans]
print(ans+1)

Submission status: Time Limit Exceeded

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

doubling = [[0] * N for _ in range(61)]
for i in range(N):
  doubling[0][i] = A[i]
  
for i in range(1,61):
  for j in range(N):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    
now = 0
i = 0
while K!=0:
  if K&1==1:
    now = doubling[i][now]
    K = K>>1
    i += 1
    
  else:
    K = K>>1
    i += 1
    
print(now+1)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,k=[int(_) for _ in input().split()]
A=[int(_) for _ in input().split()]
dub=[x for x in set(A) if A.count(x)>1]
dub.append(1)
count=0
t=0
s=1
flag=0
while True: 
    s=A[s-1]
    t+=1
    if s in dub:
        r=s
        while True:
            s=A[s-1]
            count+=1
            if s==r:
                flag=1
                break
    if flag==1:
        break
t+=(((k-t)//count)-1)*count
while True: 
    s=A[s-1]
    t+=1
    if t>=k:
        print(s)
        break

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lis = list(map(lambda z: int(z) - 1, map(int, input().split())))

s = [0]
res = [0]

while lis[res[-1]] not in s:
    res.append(lis[res[-1]])
    s.append(res[-1])

x, y = res.index(lis[res[-1]]), len(res)

if m < y:
    print(res[m] + 1)
else:
    mm = (m - x) % (y - x)
    print(res[mm + x] + 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = np.zeros((N, 2))

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
mem[c] += 1
mem[c][1] = 0
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    mem[c][0] += 1
    if np.any(mem.T[0]>1):
        T = k - mem[c][1]
        cK = k
        flg = False
        break
    mem[c][1] = k

if flg:
    print(c+1)
else:
    iterN = int(np.mod(int(K - cK), int(T)))
    for i in range(iterN):
        c = A[c]
    print(c+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def make_my_route(route,A,N):
    pre = 1
    for i in range(N):
        now = A[pre-1]
        route = np.append(route,now)
        temp = np.sum(route == now)
        if temp == 2:
            break
        pre = now
    return route


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    route = np.array([1])

    route = make_my_route(route,A,N)
    now = route[-1]
    start = int(np.where(route == now)[0][0])

    if K < start:
        res = route[K]
    elif start+1 != N:
        K -= start
        loop = route[start:-1]
        # print(loop,K)
        M = len(loop)
        K %= M
        res = loop[K]
    else:
        res = route[K]

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
loop_start = 0
loop = 0
for i in range(n):
    ans.append(a[ans[i] - 1])
for j in ans:
    if j in ans[:loop_start] or j in ans[loop_start+1:]:
        break
    loop_start += 1
loop = ans[loop_start+1:].index(j) + 1
ans.clear()
ans = [1]
if k < loop_start:
    for l in range(k):
        ans.append(a[ans[l] - 1])
    print(ans[k])
else:
    for l in range(loop_start + loop):
        ans.append(a[ans[l] - 1])
    print(ans[((k-loop_start)%loop)+loop_start])

Submission status: Time Limit Exceeded

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

if num2==0:
    print(list[K%len(list)])
else:
    if K<=num2:
        print(list[K%len(list)])
    else:
        num=(K-num2)%(len(list)-num2)
        print(list[num+num2])

Submission status: Time Limit Exceeded

Solution code:
def d():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # print('A = {}'.format(A))
    warps = [1]

    for i in range(K):
        city = A[warps[-1] - 1]
        # print('city, warps = {}, {}'.format(city, warps))
        if city in warps:
            loop_start_index = warps.index(city)
            Kn = (K - loop_start_index) % (len(warps) - loop_start_index)
            print(warps[loop_start_index + Kn])
            return
        else:
            warps.append(city)
    print(warps[-1])


##########
if __name__ == "__main__":
    d()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  N, K = map(int, input().split())
  route = list(map(int, stdin.readline().split()))
  n_place = 1
  trails = [1]
  pos_num = [0] * N
  flg = 0
  if N < K:
    for i in range(N):
      n_place = route[n_place - 1]
      pos_num[n_place-1] += 1
      if pos_num[n_place-1] == 2:
        j = trails.index(n_place)
        start = j
        kyori = i - j + 1
        loop = trails[start : start + kyori]
        flg = 1
        break
      else:
        trails.append(n_place)
      if i == K - 1:
        print(n_place)
    if flg == 1:
      print(loop[(K - start) % kyori])
  else:
    for i in range(K):
      n_place = route[n_place - 1]
      if n_place in trails:
        j = trails.index(n_place)
        start = j
        kyori = i - j + 1
        loop = trails[start : start + kyori]
        flg = 1
        break
      else:
        trails.append(n_place)
      if i == K - 1:
        print(n_place)
    if flg == 1:
      print(loop[(K - start) % kyori])
main()

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
c = copy(a)
ans = 0
while k:
    if k & 1:
        ans = c[ans]
    t = copy(c)
    for i in range(n):
        t[i] = c[c[i]]
    c = copy(t)
    k >>= 1
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
def d():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # print('A = {}'.format(A))
    warps = [1]

    for i in range(K):
        city = A[warps[-1] - 1]
        # print('city, warps = {}, {}'.format(city, warps))
        if city in warps:
            loop_start_index = warps.index(city)
            loop = warps[loop_start_index:]
            K -= loop_start_index
            print(loop[K % len(loop)])
            return
        else:
            warps.append(city)
    print(warps[-1])


##########
if __name__ == "__main__":
    d()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), dtype='int')
len_max = n
array1 = [1]
now_city = 1
loop = 0
flg = 0

for i in range(k):
    now_city = a[now_city - 1]
    if np.any(array1 == now_city) and i != 0:
        flg = 1
        loop_begin = np.where(array1 == now_city)[0][0]
        loop_end = i + 1

        now_city = 1
        for i in range(loop_begin):
            now_city = a[now_city - 1]
        k -= loop_begin
        loop = loop_end - loop_begin
        k = k % loop
        for i in range(k):
            now_city = a[now_city - 1]
        ans = now_city

        break
    if i < len_max:
        array1.append(now_city)

    if i == k - 1:
        ans = now_city
   

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(lambda x:int(x)-1,readline().split()))

    d=[]
    x=0
    while pow(2,x)<k:
        li=[0]*n
        if x==0:
            for i in range(n):
                li[i]=a[i]
            d.append(li)
        else:
            for i in range(n):
                j=d[x-1][i]
                li[i]=d[x-1][j]
            d.append(li)
        x+=1

    l=bin(k)[2:]
    x=len(l)
    ans=0
    for i in range(x):
        j=x-i-1
        if l[i]=="1":
            ans=d[j][ans]

    print(ans+1)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
n,k=[int(_) for _ in input().split()]
A=[int(_) for _ in input().split()]
vlist=deque()
vlist.append(0)
dub=[x for x in set(A) if A.count(x)>1]
count=0
t=0
s=1
while True: 
    s=A[s-1]
    t+=1
    if s in dub:
        r=s
        while True:
            s=A[s-1]
            count+=1
            if s==r:
                break
        t+=((k-t)//count)*count
    if t>=k:
        print(s)
        exit()

Submission status: Time Limit Exceeded

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

DB = [[0] * (n + 1) for _ in range(max_k + 1)]
# DB[i][j] 2**i乗回考えた時にjが移動する数
for j in range(1, n + 1):
    DB[0][j] = A[j]
for i in range(max_k):
    for j in range(1, n + 1):
        num = DB[i][j]
        DB[i + 1][j] += DB[i][num]
bit = bin(k)
num = 1
for i in range(max_k):
    if bit[-(i + 1)] == "1":
        num = DB[i][num]
print(num)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
while True:  
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l.index(l[-1])

loop = len(l[last:-1])
first = len(l[:last])
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0
print(B[k-1])

Submission status: Time Limit Exceeded

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

n = 1
visit = [1]
for i in range(K):
    n = A[n-1]
    if n in visit:
        loop = [n]
        m = n
        while True:
            m = A[m-1]
            if m == n:
                print(loop[(K-len(visit)+1)%len(loop)-1])
                break
            loop += [m]
        break
    visit += [n]
else:
    print(visit[K])

Submission status: Time Limit Exceeded

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

d = 1
count = 0
loop = []
route = [1]

while count < len(data):
    d = data[d-1]
    if d in route:
        loop = route[route.index(d):]
        break
    else:
        route.append(d)
    count += 1
if len(loop) > 0:
    loop_len = len(loop)
    a = len(route) - loop_len
    if k < a:
        print(route[k])
    else:
        print(loop[(k-a)%loop_len])
else:
    print(route[k])

Submission status: Time Limit Exceeded

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

now = 1
toLoop = 0 #1の町からループに入るまでのワープ数
towns = list()
townList = list()
for i in range(1,K+1):
	now = A[now-1]
	loop_num = i
	if not now in towns:
		towns.append(now)
	else:
		start = now
		count = 1
		now = A[now-1]
		while start != now:
			count += 1
			now = A[now-1]
		toLoop = loop_num - count
		loop_num = count
		break

if K <= loop_num:
	print(now)
else:
	warp_num = (K-toLoop)%loop_num
	for _ in range(warp_num): now = A[now-1]
	print(now)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
city = 1
cities = [city]
remain = []
remain_count = 0
loop = []
loop_count = 0
cities_append = cities.append
while True:
    city = A[city-1]
    if city in cities:
        remain_count = cities.index(city)
        remain = cities[:remain_count-1]
        loop = cities[remain_count:]
        loop_count = len(loop)
        break
    else:
        cities_append(city)

result = int()
if K < remain_count:
    result = remain[K]
else:
    result = loop[(K - remain_count) % loop_count]

# 結果出力
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = input().split()
N = int(n[0])
K = int(n[1])

lista = []
listb = [1]
C = 1
A = list(map(int, input().split()))
                 
for i in range(2*10**5 + 2):
    C = A[C-1]
    if C not in listb:
        listb.append(C)
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[D+M])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

n,k,*a = list(map(int,read().split()))
for i in range(n): a[i] -= 1

def pow2(a,n):
    if n==0: return list(range(n))
    if n==1: return a
    if n%2:
        return mul(a,pow2(a,n-1))
    else:
        x = pow2(a,n//2)
        return mul(x,x)

def mul(a,b):
    return [a[bi] for bi in b]

x = pow2(a,k)
print(x[0]+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import sys
import numpy as np
sys.setrecursionlimit(4*(10**5)+1)

class Args(object):
    def __init__(self, N):
        self.num_of_transition = 0
        self.path = []
        self.count_visit_node_i = [0] * N
        self.ith_visit_node_i = [-1] * N

def solve(N, K, A):
    args = Args(N)

    def walk(p):
        tmp = args.ith_visit_node_i[p]
        args.ith_visit_node_i[p] = args.num_of_transition
        args.num_of_transition += 1
        args.path.append(p)
        args.count_visit_node_i[p] += 1
        if max(args.count_visit_node_i) > 1:
            args.count_step_before_roop = tmp
            return
        return walk(A[p]-1)

    walk(0)
    roop_start_node_i = np.argsort(args.count_visit_node_i)[-1]
    #print(args.num_of_transition)
    #print(args.path)
    #print(args.count_visit_node_i)
    #print(roop_start_node_i, args.count_step_before_roop, args.ith_visit_node_i)

    freq = collections.Counter(args.count_visit_node_i)

    const_step = args.count_step_before_roop

    roop_step = sum(args.count_visit_node_i) - const_step - 1 #double count

    if K < const_step:
        ans_step = K
    else:
        ans_step = (K-const_step) % roop_step + const_step

    #print(const_step, roop_step, ans_step)

    ans_args = Args(N)

    def walk_ans(p):
        if ans_args.num_of_transition == ans_step:
            ans_args.ans = p + 1
            return
        ans_args.num_of_transition += 1
        ans_args.path.append(p)
        walk_ans(A[p]-1)

    walk_ans(0)
    print(ans_args.ans)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    solve(N, K, A)

if __name__ == '__main__':
    main()