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:
def check(n,seq):
    for i in range(len(seq)):
        if n == seq[i]:
            return True
    return False

if __name__ == '__main__':
    nk = input()
    nk = nk.split()
    n = int(nk[0])
    k = int(nk[1])

    A_N = input()
    A_N = A_N.split()
    a_n = list(map(int,A_N))

    now = 1
    nows = [0]*(n+1)
    nows[0] = now
    nows[n] = now
    for i in range(n+1):
        now = a_n[now-1]
        if check(now,nows):
            target = now
            target_loc = i
            break
        nows[i+1] = now

    start = nows.index(target) 
    end = target_loc+1
    new_now = nows[start:end]
    if k >= start:
        k -= start
        m = len(new_now)
        print(new_now[k%m])
    else:
        print(nows[k-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[a-1 for a in A]
Appeared=[]
k=0
location=0
T=0
T_List=[]
while k<=K:
    k+=1
    Appeared.append(location)
    location=A[location]
    if location in Appeared:
        T=k-Appeared.index(location)
        T_List=Appeared[k-T:k]
        break
if len(T_List)==0:
    print(Appeared[-1]+1)
else:
    Destination=(K-(k-T-1))%T
    print(T_List[Destination-1]+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve2():
    # ダブリング
    n, k = map(int, input().split())
    to = [[-1] * n for _ in range(60)]
    to[0] = list(map(lambda x: int(x) - 1, input().split()))

    # 2^i回テレポートした後何処にいるのか？
    for i in range(59):
        for j in range(n):
            to[i + 1][j] = to[i][to[i][j]]

    v = 0
    for i in reversed(range(60)):
        l = 1 << i
        if l <= k:
            v = to[i][v]
            k -= l

    print(v + 1)


if __name__ == '__main__':
    resolve2()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def has_duplicates(seq):
    return len(seq) != len(set(seq))

if __name__ == '__main__':
    nk = input()
    nk = nk.split()
    n = int(nk[0])
    k = int(nk[1])

    A_N = input()
    A_N = A_N.split()
    a_n = list(map(int,A_N))

    now = 1
    nows = [0]*(n+1)
    nows[0] = now
    nows[n] = now
    for i in range(n):
        now = a_n[now-1]
        nows[i+1] = now
        if has_duplicates(nows):
            target = now
            target_loc = i

    start = nows.index(target)-1
    end = target_loc
    new_now = nows[start:end]

    k -= start
    m = len(new_now)

    print(new_now[k%m])

Submission status: Time Limit Exceeded

Solution code:

if __name__ == '__main__':
    nk = input()
    nk = nk.split()
    n = int(nk[0])
    k = int(nk[1])

    A_N = input()
    A_N = A_N.split()
    a_n = list(map(int,A_N))

    now = 1
    nows = [0]*(n+1)
    nows[0] = now
    nows[n] = now
    for i in range(n):
        now = a_n[now-1]
        for j in range(len(nows)):
            if now == nows[j]:
                target = now
                target_loc = i
        nows[i+1] = now

    start = nows.index(target)-1
    end = target_loc
    new_now = nows[start:end]

    k -= start
    m = len(new_now)

    print(new_now[k%m])

Submission status: Time Limit Exceeded

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

doubling = []
lst = []
for i in range(n):
    lst.append(a[i])
doubling.append(lst)

for i in range(59):
    before = doubling[-1]
    after = []
    for j in range(n):
        after.append(before[before[j]])
    doubling.append(after)

sisu = 59
now = 0
while k > 0:
    idx = pow(2, sisu)
    if k < idx:
        sisu -= 1
    else:
        k -= idx
        now = doubling[sisu][now]
print(now+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(v) for v in input().split(" ")]
Ai = [int(v) for v in input().split(" ")]
assert len(Ai) == N


path = [0]
while True:
  next_city = Ai[path[len(path) - 1]] - 1
  if next_city in path:
    break
  path.append(next_city)
  if len(path) - 1 == K:
    print(next_city + 1)
    exit()

for i, city in enumerate(path):
  if city == next_city:
    start = path[:i]
    circle = path[i:]
    break

if K <= len(start):
  print(start[K] + 1)
else:
  K -= len(start)
  print(circle[K % len(circle)] + 1)

Submission status: Time Limit Exceeded

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

v = [[-1]*N for i in range(61)]
v[0] = A[:]
now = 0
for i in range(60):
    for j in range(N):
        v[i+1][j] = v[i][v[i][j]]
    if K>>i & 1:
        now = v[i][now]
print(now + 1)

Submission status: Time Limit Exceeded

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

v = [A[:]]
now = 0
for i in range(60):
    v.append([v[i][v[i][j]] for j in range(N)])
    if K>>i & 1:
        now = v[i][now]
print(now + 1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
ts = []

t = 0
for i in range(N):
    ts.append(t)
    t = As[t]-1
    if t in ts:
        break

d = ts.index(t)
p = i - d + 1

if K > d:
    idx = (K - d) % p + d
else:
    idx = K

print(ts[idx]+1)

Submission status: Time Limit Exceeded

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

i=1
k=0

while K > k:
  i = li[i-1]
  k = 1 + k

print(i)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
history = [-1]*N

location = 0
for i in range(N+1):
    history[i] = location
    location = As[location]-1
    if location in history:
        break

lead = history.index(location)
loop = i - lead + 1

if K > lead:
    idx = (K - lead) % loop + lead
else:
    idx = K

print(history[idx]+1)

Submission status: Time Limit Exceeded

Solution code:
#ダブリングを用いる解法
from sys import stdin
import math

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

log2_K = math.ceil(math.log2(K))
matrix = [A] + [[0]*N for _ in range(log2_K - 1)]
for j in range(1,log2_K):
    for i in range(N):
        idx = matrix[j-1][i] - 1
        matrix[j][i] = matrix[j-1][idx]

position = 1
row = [i for i in range(1,N+1)]

for j in range(log2_K):
    if (K >> j & 1) == 1:
        newrow = [0]*N
        for i in range(N):
            idx = matrix[j][i] - 1
            newrow[i] = row[idx]
        row = newrow

print(row[0])

Submission status: Time Limit Exceeded

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

ans=0
now=1
i=1
result=[1]
while i<=k:
    now=a[now-1]
    if now in result:
        x=result.index(now)
        length=i-x
        ans=result[(k-x)%length+x]
        break
    result.append(now)
    i+=1
    
if ans!=0:
    print(ans)
else:
    print(result[-1])

Submission status: Time Limit Exceeded

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

ans=0
now=1
i=1
result=[1]
while i<=k:
    now=a[now-1]
    if now in result:
        x=result.index(now)
        length=i-x
        ans=result[(k-x)%length+x]
    result.append(now)
    i+=1
    
if ans!=0:
    print(ans)
else:
    print(result[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N,K = map(int, stdin.readline().split())
A = [0] + list(map(int, stdin.readline().split()))
move = [1]
for _ in range(1,N+1):
    nxt = A[move[-1]]
    move.append(nxt)

if N >= K:
    print(move[K])
    exit()
    
start_roop = -1
end_roop = -1
for i in range(1,N+1):
    num = move[i]
    for j in range(i):
        if move[j] == num:
            start_roop = j
            end_roop = i
            break
    if start_roop != -1:
        break

if start_roop != -1:
    roop_length = end_roop - start_roop
    mod = (K - start_roop)%roop_length
    ans = move[start_roop + mod]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(x) - 1 for x in input().split()]
now = 0
b = [0] * n
while k!= 0:
    if k & 1:
        now = a[now]
    k >>= 1
    for i in range(n):
        b[i] = a[a[i]]
    a = b[:]
print(now+1)

Submission status: Time Limit Exceeded

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


def main() -> None:
    N, K = rmi()
    A = rmi()
    route = []
    current = 1
    for n in range(N):
        if not current in route:
            route.append(current)
            current = A[current - 1]
        else:
            route.append(current)
            break
    dup = route[-1]
    dup_index = route.index(dup)
    roop_range = len(route) - dup_index - 1
    if K < dup_index:
        w(route[K])
    else:
        w(route[dup_index:][(K - dup_index) % roop_range])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Time Limit Exceeded

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


def main() -> None:
    N, K = rmi()
    A = rmi()
    route = []
    current = 1
    for n in range(N):
        if not current in route:
            route.append(current)
            current = A[current - 1]
        else:
            route.append(current)
            break
    dup = [town for town in set(route) if route.count(town) > 1][0]
    dup_index = route.index(dup)
    roop_range = len(route) - dup_index - 1
    if K < len(route):
        w(route[K])
    else:
        w(route[dup_index:][(K - dup_index) % roop_range])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
    if next_machi in machi_list:
        break
    count += 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1
z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

Submission status: Time Limit Exceeded

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

teleporter = 1
for k in range(K):
    teleporter = A[teleporter-1]

print(teleporter)

Submission status: Time Limit Exceeded

Solution code:
# Author : code_marshal


n, k = map(int, input().split())
teleport = list(map(int, input().split()))
i = s = 1
while k:
    s = i = teleport[i-1]
    k-=1
print (s)

Submission status: Time Limit Exceeded

Solution code:


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

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

visited = [0]

now = 0
next = -1

while True:
    next = A[now]-1
    if next in visited:
        break
    else:
        now = next
        visited.append(now)

if m < len(visited):
    print(visited[m]+1)
else:
    loop = len(visited)-visited.index(next)
    m-=(len(visited)-loop)
    print(visited[m%loop+visited.index(next)]+1)

Submission status: Time Limit Exceeded

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

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]

    dv = []
    for _ in range(int(math.log2(K)) + 1):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, int(math.log2(K)) + 1):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(60):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in reversed(a):
        now = dv[i][now]
    print(now + 1)





    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]

    dv = []
    for _ in range(60):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, 60):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(60):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in reversed(a):
        now = dv[i][now]
    print(now + 1)





    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
An = list(map(int,input().split()))
a = An[0]
b = []
counter = 0
for i in range(K-1):
    a = An[a-1]
    b += [a]
    counter += 1
    f = list({a,a}&set(b))
    if f == [a,a]:
        c = b[b.index(a):]
        d = (K - counter - b.index(a) ) % len(c)
        for k in range(d-1):
            a = An[a-1]
        print(a)
        break
    elif i == K-2:
        print(a)
        break

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
An = list(map(int,input().split()))
a = An[0]
b = []
counter = 0
for i in range(K-1):
    a = An[a-1]
    b += [a]
    counter += 1
    f = list({a,a}&set(b))
    if f == [a,a]:
        c = b[b.index(a):]
        d = (K - counter - b.index(a) ) % len(c)
        for i in range(d-1):
            a = An[a-1]
        print(a)
        break
    elif i == K-2:
        print(a)

Submission status: Time Limit Exceeded

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

    ans = [1]
    for _ in range(n-1):
        if a[ans[-1]-1] in set(ans):
            start = ans.index(a[ans[-1]-1])
            break
        ans.append(a[ans[-1]-1])

    if k > start:
        index = (k - start) % (len(ans) - start) + start
        t = ans[index]
    else:
        t = ans[k]
    return print(t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
next_visit = 0
visited = [0]
for i in range(k):
  next_visit = a[next_visit] - 1
  if next_visit in set(visited):
    break
  visited.append(next_visit)
 
loop = visited[visited.index(next_visit):]
amari = (k - i - 1) % len(loop)
 
print(loop[amari]+1)

Submission status: Time Limit Exceeded

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

path = [1]
current_pos = 1
detect_loop = False

while not detect_loop:
    current_pos = A[current_pos - 1]
    if current_pos in path:
        detect_loop = True
    path.append(current_pos)

loop = path[(idx := path.index(current_pos)):-1]
straight = path[:idx]

if K < len(straight):
    print(straight[K])
else:
    print(loop[(K - len(straight)) % len(loop)])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
for i in range(k+1):
    #print(dum,ans_list,i,k)
    if ok and ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False

    if k == 0:
        print(int(dum))
        break
    if ok:
        ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
l=list(map(int,input().split()))
N=l[0]
K=l[1]
L=list(map(int,input().split()))
L=np.array(L)
a=L[0]
v=0
X=np.zeros(N, dtype = int)
Y=np.zeros(N, dtype = int)
X[0]=1
Y[0]=0
for i in range(K):
    b=a
    if X[b-1]==1:
        k1=Y[b-1]
        k2=i+1-k1
        v=1
        A=np.zeros(N, dtype = int)
        A[a-1]=1
        a=np.dot(L,A)
        break
    X[a-1]+=1
    Y[a-1]=i+1
    A=np.zeros(N, dtype = int)
    A[a-1]=1
    a=np.dot(L,A)
    
if v==1:
    K=(K-k1)%k2
    for i in range(K):
        b=a
        A=np.zeros(N, dtype = int)
        A[a-1]=1
        a=np.dot(L,A)


print(b)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))         # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
while(1):
    #print(dum,ans_list)
    if ok and ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False

    if k == 0:
        print(int(dum))
        break
    if ok:
        ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))         # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
while(1):
    #print(dum,ans_list)
    if ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False

    if k == 0:
        print(int(dum))
        break
    if ok:
        ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))         # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
while(1):
    #print(dum,ans_list)
    if ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        #print("ok")

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1

Submission status: Time Limit Exceeded

Solution code:
#ループを見つける解法
from sys import stdin

N,K = map(int, stdin.readline().split())
A = [0] + list(map(int, stdin.readline().split()))
#1,3,4,1,3
move = [1]
for _ in range(1,N+1):
    nxt = A[move[-1]]
    move.append(nxt)

if N >= K:
    ans = move[K]
else:
    start_roop = -1
    end_roop = -1
    for i in range(1,N+1):
        num = move[i]
        for j in range(i):
            if move[j] == num:
                start_roop = j
                end_roop = i
                break
        if start_roop != -1:
            break

    if start_roop != -1:
        roop_length = end_roop - start_roop
        mod = (K - start_roop)%roop_length
        ans = move[start_roop + mod]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def doubling(n,k,a):
    logk = 1
    beki = 2
    while beki < k:
        logk += 1
        beki = beki << 1
    dp = [[0 for _ in range(n)] for _ in range(logk)]
    for i in range(n):
        dp[0][i] = a[i]
    for i in range(logk-1):
        for j in range(n):
            dp[i+1][j] = dp[i][dp[i][j]]
    now = 0
    index = 0
    while k > 0:
        if k&1:
            now = dp[index][now]
        k = k >> 1
        index += 1
    return now+1


def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    for i in range(n):
        a[i] -= 1
    print(doubling(n,k,a))    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def doubling(n,k,a):
    logk = 1
    while pow(2,logk) < k:
        logk += 1
    dp = [[0 for _ in range(n)] for _ in range(logk)]
    for i in range(n):
        dp[0][i] = a[i]
    for i in range(logk-1):
        for j in range(n):
            dp[i+1][j] = dp[i][dp[i][j]]
    now = 0
    index = 0
    while k > 0:
        if k&1:
            now = dp[index][now]
        k = k >> 1
        index += 1
    return now+1


def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    for i in range(n):
        a[i] -= 1
    print(doubling(n,k,a))    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a=[-1]*N
b=1
for i in range(N):
    if not b in a:
        a[i]=b
        b=List[b-1]
    else:
        c=i
        break
#print(a)
#print(b,c)
num=a.index(b)
#print(T,num)
T=c-num
if K<num:
    print(a[K])
else:
    print(a[num:][(K-num)%T])

Submission status: Time Limit Exceeded

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

    ans = [1]
    for _ in range(n):
        if a[ans[-1]-1] in ans:
            start = ans.index(a[ans[-1]-1])
            break
        ans.append(a[ans[-1]-1])

    if k > start:
        index = (k - start) % (len(ans) - start) + start
        t = ans[index]
    else:
        t = ans[k]
    return print(t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a=[]

for i in range(N):
    a.append(-1)
#print(a)
b=1
for i in range(N):
    if not b in a:
        a[i]=b
        b=List[b-1]
    else:
        c=i
        break
#print(a)
#print(b,c)
num=a.index(b)
#print(T,num)
T=c-num
if K<num:
    print(a[K])
else:
    print(a[num:][(K-num)%T])

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    l[0] = 0
    ans = -100

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

    for i in range(n*3):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break

    print(max(ans, -1))

main()

Submission status: Time Limit Exceeded

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

    t = 1
    ans = [1]
    while True:
        if a[t-1] in ans:
            start = ans.index(a[t-1])
            break
        ans.append(a[t-1])
        t = a[t-1]

    if k > start:
        index = (k - start) % (len(ans) - start) + start
        t = ans[index]
    else:
        t = ans[k]
    return print(t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*200010
    now = 0
    l[0] = 0
    ans = -100

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

    for i in range(n*2):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break

    print(max(ans, -1))

main()

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*200010
    now = 0
    l[0] = 0
    ans = -100

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

    for i in range(n*4):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break
        
    print(max(ans, -1))

main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [-1]*200010
now = 0
l[0] = 0
ans = -100

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

for i in range(n*4):
    k -= 1
    now = a[now] #転送された場所
    l[now] += 1
    if l[now] == 2: #3ループ目の頭
        loop = l.count(1) + 1
        k %= loop
    if k == 0:
        ans = now + 1
        break

print(max(ans, -1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

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

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

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

from math import log2

class Doubling:
    def __init__(self, lst, max_step):
        self.lst = lst
        self.max_step = max_step
        self.k = int(log2(max_step * 2 - 1)) + 1
        # print(self.k)
        self.D = self.create()

    def create(self):
        len_ = len(self.lst)
        D = [[-1] * len_ for _ in range(self.k)]
        D[0] = self.lst
        d = 2
        for i in range(1, self.k):
            for j in range(len_):
                D[i][j] = D[i - 1][D[i - 1][j]]
            d *= 2
        # print(D)
        return D

    def step(self, start, step):
        v = start
        for i in range(self.k, -1, -1):
            l = 1 << i
            if l <= step:
                v = self.D[i][v]
                # print(i, l)
                step -= l
        return v

def solve():
    n, k = MI()

    A = LI1()
    d = Doubling(A, k)

    v = d.step(0, k)
    print(v+1)


if __name__ == '__main__':

    solve()

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(n) for n in input().split()]
A = {i : int(n) for i, n in enumerate(input().split())}
#print(A)
next_city = 1
for i in range(K):
  if i == 0:
    cur = i
  else:
    cur = next_city -1
  #print(cur)
  next_city = A[cur]
print(next_city)

Submission status: Time Limit Exceeded

Solution code:
def isInt(x):
    try:
        float(x)
    except ValueError:
        return False
    else:
        return float(x).is_integer()

def main():
    try:
        str = input().split()
    except ValueError:
        return

    if isInt(str[0]):
        N = int(str[0])
    else:
        return

    if not( 2 <= N and N <= 2*10**5):
        return

    if isInt(str[1]):
        K = int(str[1])
    else:
        return

    if not( 1 <= K and K <= 10**18):
        return

    try:
        str = input().split()
    except ValueError:
        return

    A = [0] * N
    for i in range(N):
        if isInt(str[i]):
            ai = int(str[i])
            if 1 <= ai and ai <= N:
                A[i] = ai
            else:
                return
        else:
            return
    
    now = 1
    path = [1]
    while(True):
        now = A[now-1]
        if now in path:
            loopstart = path.index(now)
            break
        else:
            path.append(now)

    if K < loopstart:
        print (path[K])
    else:
        print (path[loopstart + (K-loopstart)%(len(path)-loopstart)])

def main2():    
    str = input().split()
    N = int(str[0])
    K = int(str[1])
    str = input().split()
    A = []
    for i in range(N):
        A.append(int(str[i]))
    
    now = 1
    path = [1]
    while(True):
        now = A[now-1]
        if now in path:
            loopstart = path.index(now)
            break
        else:
            path.append(now)

    if K < loopstart:
        print (path[K])
    else:
        print (path[loopstart + (K-loopstart)%(len(path)-loopstart)])
        
if __name__ == '__main__':
    main2()

Submission status: Time Limit Exceeded

Solution code:
def isInt(x):
    try:
        float(x)
    except ValueError:
        return False
    else:
        return float(x).is_integer()

def main():
    try:
        str = input().split()
    except ValueError:
        return

    if isInt(str[0]):
        N = int(str[0])
    else:
        return

    if not( 2 <= N and N <= 2*10**5):
        return

    if isInt(str[1]):
        K = int(str[1])
    else:
        return

    if not( 1 <= K and K <= 10**18):
        return

    try:
        str = input().split()
    except ValueError:
        return

    A = [0] * N
    for i in range(N):
        if isInt(str[i]):
            ai = int(str[i])
            if 1 <= ai and ai <= N:
                A[i] = ai
            else:
                return
        else:
            return

    now = 1
    path = [1]
    while(True):
        now = A[now-1]
        if now in path:
            loopstart = path.index(now)
            break
        else:
            path.append(now)
    if K < loopstart:
        print (path[K])
    else:
        print (path[loopstart + (K-loopstart)%(len(path)-loopstart)])
        
if __name__ == '__main__':
    main()