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: Accepted

Solution code:
import sys

# print('input >>')
N, K = map(int,(input().split()))
As = list(map(lambda x: int(x)-1,(input().split())))

visited = [0] * N
visited[0] = 1
roots = [0]
now = 0

# print('-----output-----')
while True:
    now = As[now]
    if visited[now] == 1:
        p = now
        rep_start = roots.index(now)
        move = len(roots) - rep_start
        break
    roots.append(now)
    visited[now] = 1

now = 0
if rep_start > K:
    for i in range(K):
        now = As[now]
    print(now+1)
    sys.exit()

# now = p
# for i in range(rep_start):
    # now = As[now]


K -= rep_start
K %= move
now = p

# print('K', K)
# print('now',now)

for i in range(K):
    now = As[now]

print(now+1)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
a = []
a.append(np.array(list(map(int, input().split()))) - 1)
for _ in range(60):
    a.append(a[-1][a[-1]])
ans = 0
i = 0
while k > 0:
    if k & 1:
        ans = a[i][ans]
    i += 1
    k //= 2
print(ans + 1)

Submission status: Accepted

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


curr = 0
arr = []
visited = [False]*n
while(not visited[curr]):
    visited[curr] = True
    arr.append(curr)
    curr = a[curr]-1

visited = [False]*n
cycleSize = 0
while(not visited[curr]):
    visited[curr] = True
    cycleSize+=1
    curr = a[curr]-1

pathSize = len(arr) - cycleSize

if(pathSize>=k):
    print(arr[k]+1)
else:
    print(arr[(k-pathSize)%cycleSize+pathSize]+1)

Submission status: Accepted

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

l=[1]
x=1
cnt=[0 for n in range(N)]
cnt[0]=1
for n in range(N):
    y=A[x-1]
    l.append(y)
    cnt[y-1]+=1
    x=y
    if cnt[y-1]==2:
        value=y
        temp=n
        break

for m in range(len(l)):
    if l[m]==value:
        bias=m
        mul=temp-bias+1
        break
    
if bias>K:
    print(l[K])
else:
    print(l[bias+(K-bias)%mul])

Submission status: Accepted

Solution code:
num_town, num_move = map(int, input().split())
teleports = list(map(lambda x: int(x) - 1, input().split()))

current = 0
memo = {}
for i in range(num_move):
    if memo.get(current) == 2:
        break
    if not memo.get(current):
        memo[current] = 1
    else:
        memo[current] += 1
    destination = teleports[current]
    current = destination

loop = {k:v for k,v in memo.items() if v==2}
minus = {k:v for k,v in memo.items() if v==1}

new_move_count = 0
if len(loop) == 0:
    current = 0
    new_move_count = num_move
else:
    new_move_count = (num_move - len(minus)) % len(loop)

for i in range(new_move_count):
    destination = teleports[current]
    current = destination

print(current + 1)

Submission status: Accepted

Solution code:
N = [int(e) for e in input().split()]
nums = [int(t) for t in input().split()]
count=[]
k = 0
check = []
t = nums[0]
for i in range(N[0]):
    count.append(0)
while count[t-1] == 0:
    check.append(t)
    count[t-1] += 1
    k = t -1
    t = nums[k]

s = check.index(t) + 1
if(N[1] < s):
    print(check[N[1] - 1])
else:
    ans = (N[1] - s)%(len(check)+1-s)
    ans1 = check.index(t) + ans
    print(check[ans1])

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = [0] + list(map(int,input().split()))
T = {1:1}
current_town = 1
for i in range(2,K+1):
    current_town = A[current_town]
    K -= 1
    if current_town in T:
        loop_towns = list(T.keys())[T[current_town]-1:]
        print(loop_towns[K%len(loop_towns)])
        break
    else:
        T[current_town] = i
else:
    print(A[current_town])

Submission status: Accepted

Solution code:
import numpy as np

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

    for i in range(1,k):
        go = a[foot[-1]]
        foot.append(go)
        if ed[go] == 1:
            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
        ed[go] = 1
    
    if not is_loop:
        print(a[foot[-1]]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

start=1
list=[1]
kenti=[0 for i in range(n)]
kenti[0]=1

zan=-1

for i in range(k):
  start-=1
  next=a[start]
  start=next

  if kenti[start-1]!=0:
    zan=k-(i+1)
    inx=list.index(start)
    list=list[inx:]
    break
  else:
    list.append(start)
    kenti[start-1]+=1

if zan==-1:
  print(list[-1])
  exit()
elif zan==0:
  print(list[0])
  exit()

zan%=len(list)
print(list[zan])

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N, K = isRaw()
    As = isRaw()
    ts = [0]*N
    now = 0
    lstart = 0
    lsize = 0
    d = {}
    for i in range(N):
        ts[i]=now
        d[now]=i
        now = As[now]-1
        if now in d:
            lstart=d[now]
            lsize=i-d[now]+1
            break
    if K < lstart:
        return ts[K]+1
    return ts[((K-lstart) % lsize)+lstart]+1

print(main())

Submission status: Accepted

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

n=[1]
t=1
ord=[-1]*(N+1)
ord[0]=0

while True:
    t=A[t-1]
    if ord[t] != -1:
        f=n.index(t)
        break
    n.append(t)
    ord[t]=0

k=len(n)-f

if K>=f:
    print(n[f+(K-f)%k])

else:
    print(n[K])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, K = LI()
A = LI()

D = 60
to = [[-1] * N for _ in range(D)]
to[0] = [a-1 for a in A]

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

now = 0
time = 0
while K > 0:
    if K&1:
        now = to[time][now]
    
    K >>= 1
    time += 1

print(now+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
pl=1
visit=[-1]*n
visit[0]=0
loop=0
cnt=0

while 1:
    cnt+=1
    pl=a[pl-1]
    
    
    if visit[pl-1]!=-1:
        loop=visit[pl-1]
        
        break
    visit[pl-1]=cnt
    if cnt==k:
        print(pl)
        exit()

loop_len=cnt-loop

k=(k-loop)%loop_len+loop
print(visit.index(k)+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
s = []
order = [-1] * (n+1)
l = 1
while order[l] == -1:
    order[l] = len(s)
    s.append(l)
    l = A[l-1]
new = s[order[l]:]
t = len(new)
first = len(s) - t
if k > first:
    print(new[(k-first)%t])
else:
    print(s[k])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N,K=map(int, sys.stdin.readline().split())
A=[None]+map(int, sys.stdin.readline().split())

L={}        #循環している町のみ記録。L[テレポーターの使用回数]=町の番号
visit=defaultdict(lambda: 0)    #visit[町の番号]=訪問回数
x=1         #スタート地点は常に1
cnt=0       #テレポーターの使用回数
while visit[x]<=2: #まだ未訪問だったら
    if visit[x]==2:
        L[cnt]=x
    if cnt==K:  #使用回数に達したら
        print x #現在の位置を表示
        quit()
    visit[x]+=1  #xを訪問済みに変更
    x=A[x]      #次の訪問先をセット
    cnt+=1

len_L=len(L)

LL={}
for cnt,city_num in L.items():
    LL[cnt%len_L]=city_num

print LL[K%len_L]

Submission status: Accepted

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

now = 1
loop_node = []
first_loop = 0
l = [0 for _ in range(N)]
while True:
    l[now - 1] += 1
    if l[now - 1] == 3:
        break

    if l[now - 1] == 2:
        loop_node.append(now)

    now = A[now - 1]
    first_loop += 1

loop_num = len(loop_node)
first_loop -= loop_num * 2

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    tree = [[] for _ in range(n)]
    for idx, a in enumerate(A):
        tree[idx].append(a - 1)

    def dfs(pre, dist):
        depth[pre] = dist
        for to in tree[pre]:
            if depth[to] != f_inf:
                cycle.append([depth[to], depth[pre] + 1])
                return
            else:
                dfs(to, dist + 1)

    cycle = []
    depth = [f_inf for _ in range(n)]
    dfs(0, 0)

    cycle_start = cycle[0][0]
    cycle_end = cycle[0][1]
    if k <= cycle_start:
        print(depth.index(k) + 1)
    else:
        remainder = (k - cycle_start) % (cycle_end - cycle_start)
        res = cycle_start + remainder
        print(depth.index(res) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    n, k = map(int, stdin.readline().rstrip().split())
    a = [int(x)-1 for x in stdin.readline().rstrip().split()]
    n = a[0]
    his = [-1, n]
    f = his.append
    s = set()
    while True:
        n = a[n]
        if n in s:
            f(n)
            break
        f(n)
        s.add(n)
    idx = his.index(his[-1])
    loop = len(his[his.index(his[-1]):-1])
    if len(his) > k:
        print(his[k]+1)
    else:
        t = (k - idx) % loop
        g = his[idx:-1]
        print(g[t]+1)
main()

Submission status: Accepted

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

# Douling(ダブリング)
i = 1
to = [[a for a in A]]
while pow(2, i) < K:
    t = [to[i-1][to[i-1][j]] for j in range(N)]
    to.append(t)
    i += 1

ans = 0
for j in range(i):
    if K & (1 << j) > 0:
        ans = to[j][ans]
print(ans+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
an = list(map(int, input().split()))
copyan = an[:]
i = copyan[0]
copyan[0]=10**6
movecount = 1

if i != 1:
    while True:
        memo = i
        if k == movecount:
            print(i)
            
            exit()
        i = copyan[i-1]
        
        if i >=300000:
            yokei = i%(10**6)         
            break
        copyan[memo-1]=10**6 + movecount
        movecount += 1
        
else:
    print(1)
    exit()
roopnum = movecount - yokei
x = (k-yokei)%roopnum

ans = copyan.index(10**6+yokei+x) +1
print(ans)

Submission status: Accepted

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

# Douling(ダブリング)
i = 1
to = [[a for a in A]]
while pow(2, i) < K:
    t = [to[i-1][to[i-1][j]] for j in range(N)]
    to.append(t)
    i += 1

i -= 1
ans = 0
while i >= 0:
    if K & (1 << i) > 0:
        ans = to[i][ans]
    i -= 1
print(ans+1)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int, readline().split())
A = np.int32(read().split())

A -= 1

def mult(A,B):
    return B[A]

def power(A,n):
    if not n:
        return np.arange(N)
    B = power(A,n//2)
    B = mult(B,B)
    return mult(A,B) if n & 1 else B

print(power(A, K)[0] + 1)

Submission status: Accepted

Solution code:
n,k = map(int, input().split()) #右の要素に対して左の関数を適応する
a = list(map(int, input().strip().split())) #strip()は文字列の両端の空白や改行を削除する

for i in range(len(a)):
    a[i] -= 1 #入力値を添字に合わせる

visited = [-1] * n #[-1. -1. -1. …]を定義
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now] #次に移動する場所
    if visited[next] >= 0:
        r = i-visited[next] #途中から繰り返される場合もあるのでそこまでにかかった回数を引いている
        pre_roop = visited[next] #ループしない部分の回数を代入
        pos = next #ループが始まる場所を代入
        break #同じ場所に帰ってきたらfor文を抜け出す
    else:
        visited[next] = i
        now = next
        i += 1

if i > k:
    print(now + 1) #今いる場所を出力
else:
    l = (k - pre_roop) % r
    i = 0
    p = pos #ループが開始される部分からスタート
    for _ in range(l):
        p = a[p]
        i +=1

    print(p+1)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = [int(i) for i in input().split()]
s = []
ord = [-1] * (n+1)
c, l = 1, 0
v = 1
while (ord[v] == -1):
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]
    
c = len(s) - ord[v]
l = ord[v]
print(s[k] if (k < l) else s[l + (k - l) % c])

Submission status: Accepted

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

# Douling(ダブリング)
i = 1
to = [[a for a in A]]
while pow(2, i) < K:
    t = [to[i-1][to[i-1][j]] for j in range(N)]
    to.append(t)
    i += 1

i -= 1
ans = [i for i in range(N)]
while i >= 0:
    if K & (1 << i) > 0:
        for j in range(N):
            ans[j] = to[i][ans[j]]
    i -= 1
print(ans[0]+1)

Submission status: Accepted

Solution code:

n,k=map(int,input().split())
a=list(map(int, input().split()))
b=[1]
ba={1}
c=0
m=0
# while flag==1:
for i in range(n):
    if a[m] not in ba:
        b.append(a[m])
        ba.add(a[m])
        c+=1
        m=a[m]-1
    else:
        e=a[m]
        break
# print(b,e,c+1)
e=b.index(e)
# print(b,e)
bc=b
b=b[e:c+1]
f=c+1-e
if c>k:
    if c-1>=k:

        print(bc[k])
        exit()
if 1 not in b:
    # print(b,f)
    ans=(k-e)%f
    print(b[ans])
else:

    ans=k%f
    print(b[ans])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a]
visited = [-1]*n
route = []
now = 0
hop = 0
while visited[now] == -1:
    visited[now]=hop
    route.append(now)
    now = a[now]
    hop+=1
loop_st = 0
for r in route:
    if r==now: break
    loop_st+=1
loop = route[loop_st:]
if k < len(route):
    print(route[k]+1)
else:
    print(loop[(k-loop_st)%len(loop)]+1)

Submission status: Accepted

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

vis_ti = [-1] * n
vis_at = [0]
now = 0

for i in range(1, k+1):
  now = a[now] - 1
  if vis_ti[now] >= 0:
    bgn = vis_ti[now]
    print(vis_at[bgn + (k - bgn) % (i - bgn)] + 1)
    sys.exit()
  vis_ti[now] = i
  vis_at.append(now)

print(vis_at[-1]+1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    tree = [[] for _ in range(n)]
    for idx, a in enumerate(A):
        tree[idx].append(a - 1)

    start = []
    depth = [0 for _ in range(n)]

    def dfs(v, p, d, cnt):
        depth[v] = d
        for u in tree[v]:
            if visited[u]:
                start.append([u + 1, depth[u], cnt + 1])
                return
            else:
                visited[u] = True
                dfs(u, v, d + 1, cnt + 1)
        return

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1, 0, 0)

    if k <= start[0][1]:
        print(depth.index(k) + 1)
    else:
        cnt = (k - start[0][1]) % (start[0][2] - start[0][1])
        res = start[0][1] + cnt
        print(depth.index(res) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

    if Rireki[to] >= 0:
        start = Jump.index(to)
        end = i
        dis = end - start

        roop = (k-start) % dis
        print(Jump[start+roop])
        break
    Rireki[to] = i
    Jump[i] = to
    next = to-1
    if i ==k:
        print(to)
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
seen = []
cnt = [-1]*n
now = 0
while cnt[now] == -1:
    cnt[now] = len(seen)
    seen.append(now)
    now = a[now]
loop = len(seen)-cnt[now]
toloop = cnt[now]
if k <= toloop:
    ans = seen[k] + 1
else:
    k = (k-toloop)%loop
    ans = seen[toloop+k] + 1
print(ans)

Submission status: Accepted

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

r = [0]*N

now = 0
r[now]=1
for i in range(N):
  now = A[now]-1
  if r[now] == 0:
    r[now] = i+2
  else:
    x1 = r[now]
    x2 = i+1
    break

roop_num = x2 - x1 + 1
x = (K-x1+1) % roop_num

if K < x1:
  print(r.index(K+1)+1)
else:
  print(r.index(x1 + x)+1)

Submission status: Accepted

Solution code:
#D
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
nxt = 1
loop = []
tset = set()
final = -1
while 1:
    loop.append(nxt)
    tset.add(nxt)
    nxt = a[nxt-1]
    if nxt in tset:
        final = nxt #重複した町
        break
m = -1
for i in range(len(loop)):
    if loop[i]==final:
        m = i
        break
l = len(loop)
if k < m:
    print(loop[k])
else:
    print(loop[(k-m)%(l-m)+m])
# print(loop[(k+1)%l])

Submission status: Accepted

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

visit=set()
order=[-1]*(N+1)
p=1
cnt=0

while not (p in visit):
    visit.add(p)
    order[cnt]=p
    p=A[p]
    cnt+=1

start=order.index(p)
end=cnt
if K>end:
    K-=(end-start)*max(0,(K-start)//(end-start)-1)
p=1
while K>0:
    p=A[p]     
    K-=1

print(p)

Submission status: Accepted

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



now = 0
past = []
past_set = set()

for i in range(N):
    if now in past_set:
        break
    past.append(now)
    past_set.add(now)
    now = A[now]


i_loop = past.index(now)
loop = past[i_loop:]
if K >= i_loop:
    print(loop[(K-i_loop) % len(loop)] +1)
else:
    print(past[K] +1)

Submission status: Accepted

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

def doubling(MAX, A):
    """ ダブリング """

    N = len(A)
    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]]
    return nxt

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

nxt = doubling(MAX, A)

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

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, K  = [int(x) for x in stdin.readline().rstrip().split()]
A = [0] + [int(x) for x in stdin.readline().rstrip().split()]

stack = [1]
nextt = A[1]
visited_dict = {1: True}

while True:
    if not visited_dict.get(nextt, False):
        stack.append(nextt)
        visited_dict[nextt] = True
    else:
        stack.append(nextt)
        break
    nextt = A[nextt]

    if len(stack) > K:
        print(stack[K])
        exit()

num1 = stack.pop()
length = len(stack)
tmp = []
while True:
    num2 = stack.pop()
    if num1 != num2:
        tmp.append(num2)
    else:
        tmp.append(num2)
        break

tmp = tmp[::-1]

index = (K - length) % len(tmp)

print(tmp[index])

Submission status: Accepted

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
*a, = map(int, input().split())
a = [a[i] - 1 for i in range(n)]
ans = 0

if k <= n:
    i = 0
    while(k > 0):
        ans = a[i]
        i = a[i]
        k -= 1
    ans += 1

else:
    # 周期と周期の場所をチェック
    start_period = 1
    period_i = -1
    # 街名に対する初めて訪れる順番の辞書
    d = defaultdict(int)
    d[0] = 1
    i = 0
    count = 1
    while(1):
        if a[i] in d.keys():
            period_i = count
            start_period = d[a[i]]
            break

        d[a[i]] = count + 1
        i = a[i]
        count += 1
        
    # 初めて訪れる順番に対する街名の逆引き辞書
    d_r = {i:k for k, i in d.items()}

    ans = d_r[start_period + ((k - (start_period - 1)) % (period_i - start_period + 1))] + 1
    
    
print(ans)

Submission status: Accepted

Solution code:
mNK = map(int, input().split())
lNK = list(mNK)

mTel = map(int, input().split())
lTel = list(mTel)

lWent = [-1 for i in range(lNK[0])]
nTown = 0
loopCnt = -1

for i in range(lNK[1]):
    nextTown = lTel[nTown] - 1
    lWent[nTown] = i
    if(lWent[nextTown] != -1):
        loopCnt = i - lWent[nextTown] + 1
        surplus = (lNK[1] - i - 1) % loopCnt
        nTown = lWent.index(lWent[nextTown] + surplus)
        break
    nTown = nextTown

print(nTown + 1)

Submission status: Accepted

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


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

    s = []
    ord = [-1] * (N+1)
    v = 1

    while ord[v] == -1:
        ord[v] = len(s)
        s.append(v)
        v = A[v-1]

    c = len(s) - ord[v]
    l = ord[v]

    if K < l:
        res = s[K]
    else:
        K -= l
        K %= c
        res = s[l+K]

    print(res)



main()

Submission status: Accepted

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

now=1
to=0
t=k
l=[0]*n
l[0]=1
cnt=2

while t>0:
    to=a[now-1]
    t-=1
    if l[to-1]!=0:
        now=to
        break
    else:
        l[to-1]=cnt
        cnt+=1
    now=to

if t==0:
    print(now)
else:
    loop=max(l)-l[to-1]+1 #loopの長さ
    start=l[to-1]-1 #start回目で開始地点
    ans=l.index((k-start)%loop+start+1)+1
    print(ans)

Submission status: Accepted

Solution code:
def solve(N, K, A):
    idx = [-1 for _ in range(len(A))]
    now = 0
    period = 0
    bias = 0
    tmp = []
    found = False
    i = 0
    while not found:
        tmp.append(now+1)
        if idx[now] == -1:
            idx[now] = i
        else:
            period = i - idx[now]
            cycle = tmp[-period-1:-1]
            bias = i - period
            break
        now = A[now]-1
        i += 1

    if K <= bias:
        now = 0
        for _ in range(K):
            now = A[now] - 1
        print(now + 1)
    else:
        K -= bias
        K = K % period
        print(cycle[K])

if __name__=="__main__":
    N,K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    solve(N, K, A)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
def warp(x,k):
    a=x
    for i in range(k):
        a=A[a-1]
    return a
count=[-1 for i in range(N)]
x=1
count[0]=0
time=0
if N>=K:
    print(warp(1,K))
else:
    for i in range(1,N+1):
        x=warp(x,1)
        if count[x-1]==-1:
            count[x-1]=i
        else:
            time=i-count[x-1]
            break;
    print(warp(1,count[x-1]+(K-count[x-1])%time))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=1
arr=[0]*(n+1)
for i in range(1,10**6):
  now=a[now-1]
  if i==k:
    print(now)
    quit()
  if arr[now]!=0:
    first=arr[now]
    break
  arr[now]=i
# print(arr)
cycle=max(arr)-first+1
# print(cycle)
mod=(k-first)%cycle
# print(mod)
ans=arr.index(first+mod)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
# A = tuple(map(lambda n: int(n) - 1, input().split()))
A = tuple(map(int, input().split()))

costs = [-1] * N
loc = 1

if K <= N:
    for i in range(K):
        loc = A[loc - 1]
    print(loc)

else:
    costs[loc - 1] = 0
    for i in range(1, K):
        loc = A[loc - 1]

        if costs[loc - 1] >= 0:
            break

        costs[loc - 1] = i

    offset = costs[loc - 1]
    loop = i - offset

    K -= i
    K %= loop

    for _ in range(K):
        loc = A[loc - 1]
    print(loc)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
pl=1
visit=[-1]*n
visit[0]=0
loop=0
cnt=0

while 1:
    cnt+=1
    pl=a[pl-1]
    if visit[pl-1]!=-1:
        loop=visit[pl-1]
        break
    visit[pl-1]=cnt
    if cnt==k:
        print(pl)
        exit()

loop_len=cnt-loop
k=(k-loop)%loop_len+loop
print(visit.index(k)+1)

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    s = []
    ord = [-1 for i in range(n + 1)]
    rep = 1
    pos = 1
    while ord[pos] == -1:
        ord[pos] = len(s)
        s.append(pos)
        pos = A[pos - 1]
        rep += 1

    rep = len(s) - ord[pos]
    # l: ループが始まる点
    l = ord[pos]
    if k < l:
        print(s[k])
    else:
        # ループが始まるまでずらす
        k -= l
        k %= rep
        print(s[l + k])
resolve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
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 print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    D = 60
    N, K = MI()
    A = LI()
    edges = [[] for i in range(N)]
    to = [[0] * N for i in range(D)]

    for i in range(N):
        to[0][i] = A[i] - 1

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

    v = 0
    for i in range(D-1, -1, -1):
        l = 1 << i
        if l <= K:
            v = to[i][v]
            K -= l

    print(v+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def main():
    N, K = map(int, input().split())
    A_i = list(map(int, input().split()))
    B_i = [0 for i in range(N)]
    cycle_list = []
    diff_list = []
    cycle = 0
    diff = 0
    counter = 0
    machi = 1

    while counter < N:
        if B_i[machi - 1] == 1:
            diff = cycle_list.index(machi)
            cycle = counter - diff
            diff_list = cycle_list[:diff]
            cycle_list = cycle_list[diff:]
            break
        else:
            counter += 1
            B_i[machi - 1] = 1
            cycle_list.append(machi)
            machi = A_i[machi - 1]

    if K < diff:
        print(diff_list[K])
    else:
        mod_K = (K - diff) % cycle
        print(cycle_list[mod_K])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

order = [-1] * N
s = []
now = 0
c = 0
a = None
b = None
while True:
    order[now] = c
    s.append(now)
    now = A[now]
    c += 1
    if order[now] >= 0:
        a = c - order[now]
        b = order[now]
        break
if K <= b:
    print(s[K] + 1)
else:
    K -= b
    K %= a
    print(s[K + b] + 1)