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 numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split()))) - 1
mem = {}

c = 0 # 現在の場所
cK = 0 # 現在の回数
flg = True
mem[c] = 0
for k in range(1, K+1):
    c = A[c] # k回目の移動先
    if c in mem:
        T = k - mem[c]
        cK = k
        flg = False
        break
    mem[c] = 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: Accepted

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

now = b[a]
S = set()
S.add(a)
while now not in S:
    S.add(now)
    now = b[now]
root = now

count = 1
now = b[root]
while now != root:
    now = b[now]
    count += 1

start = len(S) - count

if k <= start:
    now = a
    for _ in range(k):
        now = b[now]
    print(now + 1)
else:
    k -= start
    k %= count
    now = root
    for _ in range(k):
        now = b[now]
    print(now + 1)

Submission status: Accepted

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

journey = [1]

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

if K <= N:
    print(journey[K])
    exit()

loop_start = N-1
loop_end   = N
 
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: Accepted

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

costs = [-1] * N
loc = 0

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

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

        if costs[loc] >= 0:
            break

        costs[loc] = i

    offset = costs[loc]
    loop = i - offset

    K -= i
    K %= loop

    for _ in range(K):
        loc = A[loc]
    print(loc + 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] #次に移動する場所
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break #同じ場所に帰ってきたらfor文を抜け出す
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i > k:
    print(now + 1) #今いる場所を出力
else:
    l = (k - pre_roop) % r
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)

Submission status: Accepted

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

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


def dd():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    v = []
    w = {}
    now = 0
    for i in range(K):
        print('i, v, w, now = {}, {}, {}, {}'.format(i, v, w, now))
        p = A[now]
        now = p-1
        if p in w:
            j = v.index(p)
            df = i-j
            Kn = (K-i-1) % df
            p = v[j+Kn]
            break
        else:
            v.append(p)
            w[p] = p
    print(p)


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

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
q=True
k=(k-loop)%loop_len+loop
print(visit.index(k)+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
As = list(map(int, input().split()))
maps = {}

for i, a in enumerate(As):
    maps[i] = a - 1

probs = [0] * n
p = 0  # 現在位置
target = 0  # はじめて2回出現する場所
h = 0  # ターゲットの初回出現時のワープ回数
t = 0  # ターゲットの2回目の出現時のワープ回数

# はじめて2回出現する場所(target)と、その時点でのワープ回数を取得
for i in range(n + 1):
    probs[p] += 1
    if (probs[p] == 2):
        target = p
        t = i
        break
    p = maps[p]

# 初回出現位置を取得(めんどうくさいのでもう一回回した。)
p = 0
for i in range(n):
    if (p == target):
        h = i
        break
    p = maps[p]

s = t - h  # 周期
if (k <= h):
    p = 0
    for i in range(k):
        p = maps[p]
    print(p + 1)
    exit()

d = (k - h) % s  # targetに到着後にワープすべき回数

# 実際に必要な回数だけワープ
p = 0
for i in range(h + d):
    p = maps[p]

print(p + 1)

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    check=[-1]*n
    iti=0
    rireki=[]
    while True:
        iti=a[iti]-1
        if check[iti]==0:
            mae=rireki.index(iti)
            Mae=rireki[:mae]
            Loop=rireki[mae:]
            roop=len(Loop)
            break
        rireki.append(iti)

        check[iti]=0
    if k <= mae:
        print(Mae[k-1]+1)
    else:
        k-=mae
        print(Loop[(k%roop)-1]+1)
resolve()

Submission status: Accepted

Solution code:

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

loop = []
loop_corr = []
ord = [-1]*n
curr = 0
while ord[curr] == -1:
    ord[curr] = len(loop)
    loop.append(curr)
    curr = a[curr]
        
loop_corr = loop[loop.index(curr):len(loop)]

# print(loop)
# print(loop_corr)
if len(loop) > k:
    print(loop[k]+1)
else:
    diff = k - len(loop) + 1
    mod = (diff % len(loop_corr)) -1
    # print(diff)
    # print(mod)
    print(loop_corr[mod]+1)

Submission status: Accepted

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

check = [0]*N
i = 0
c = 1
check = []
visited = [0]*N
flag = False
while c<=K:
    if visited[i] == 1:
        flag = True
        break
    else:
        check.append(i)
        visited[i] = 1
        i = A[i]
        c += 1
if flag==True:
    X = check[check.index(i):]
    print(1+X[(K-check.index(i))%len(X)])  
else: 
    print(i+1)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = list(map(int, input().split()))
t = [1]
x = [0]*n
x[0] = 1
y = 1
z = 0
d = 0
flag = False
for i in range(k):
    t.append(a[t[i]-1])
    if x[a[t[i]-1]-1] != 0:
        y = x[a[t[i]-1]-1]
        z = i+2
        b = [a[t[i]-1]]
        break
    else:
        x[a[t[i]-1]-1] += i+2
        z = i+2
        b = [a[t[i]-1]]
    if i == k - 1:
        flag = True

if flag:
    print(a[t[k-1]-1])
    exit()

d = z-y


if d != 0:
    r = (k - y) % d
else:
    r = k - y

for i in range(r+1):
    b.append(a[b[i]-1])

print(b[r+1])

Submission status: Accepted

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.add(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: Accepted

Solution code:
from copy import copy
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 = copy(c)
    k >>= 1
print(ans + 1)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string,decimal
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
N,K = II()
A = LI()
flag = [False]*N
past = []
past.append(0)
now = 0
cnt = 1
for k in range(K):
  now = A[now]-1
  if flag[now]:
    past = past[past.index(now)::]
    print(past[(K - cnt) % len(past)]+1)
    exit()
  flag[now] = True
  cnt += 1
  past.append(now)
print(now+1)

Submission status: Accepted

Solution code:

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


s = []
ord = [-1] * (n+1)

v = 1
c = 1
l = 0
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - ord[v]
l = ord[v]

if l > k:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

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

Visit = [None] * N
now = 0
n = 0
while Visit[now] is None:
    Visit[now] = n
    now = As[now]-1
    n += 1
    if n == K:
        print(now+1)
        exit()

for _ in range((K-Visit[now]) % (n-Visit[now])):
    now = As[now]-1
print(now+1)

Submission status: Accepted

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

s = []
ord = [-1]*(n+1)
c = 1
l = 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]


if (k < l): print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

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

town = [0 for i in range(N+1)]

def next(A,now):
    return(A[now-1])

now = 1
i = 0
while True:
    if town[now] != 0:
        roop_start = town[now]
        roop_end = i
        break
    town[now] = i+1
    now = next(A,now)
    i += 1

roop = roop_end - roop_start + 1
teleport = min(roop_start + (K - roop_start)%roop,K)

now = 1
for i in range(teleport):
    now = next(A,now)

print(now)

Submission status: Accepted

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

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

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

tele = [0]
s = 0
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+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
q=True
v=True
cnt=0

while q:
    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)
        v=not v
        break
    if cnt==10**7:
        q=not q
if v:
    loop_len=cnt-loop
    q=True
    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()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
next = 1
List = [-1]*N
 
for i in range(K):
    if List[next-1] == -1:
        List[next-1] = i
        next = A[next-1]
 
    else:
        loop = i - List[next-1]
        afterloop = (K-(i-loop))%loop
        print(List.index((i-loop) + afterloop)+1)
        exit()
 
print(next)

Submission status: Accepted

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

H = input().split()
A = [int(z) for z in H]
B = []
s = []

for z in range(N):
	B.append(0)
	s.append(0)

C = 1
B[0] +=1
s[0] = 0

for i in range(K):
	C = A[C-1] 
	B[C-1] += 1
	if(B[C-1] == 2):
		break
	s[C-1] = i+1

r = i+1 - s[C-1]

if not r == 0:
	#uに余りを入れる
	t = (K - s[C-1])
	u = t % r
	for g in range(u):
		C = A[C-1] 

print(C)

Submission status: Accepted

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

vis = set()
vis.add(1)
cnt = 0
cnt2town = {}
town2cnt = {}
cnt2town[0] = 1
town2cnt[1] = 0

cnt = 1
prev = 1
while cnt <= K:
    a = A[prev - 1]

    if a in vis:
        c = town2cnt[a]

        rem = K - cnt
        num_loop = cnt - c

        r = rem % num_loop
        print(cnt2town[c + r])

        exit()

    cnt2town[cnt] = a
    town2cnt[a] = cnt
    vis.add(a)

    prev = a
    cnt += 1


print(a)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
flag=0
now=0
i=0
count=0
c=[0]*N
r=[0]
c[0]=1
while flag==0:
  now=A[now]-1
  count+=1
  if count==K:
    flag=1
  elif c[now]==1:
    flag=2
  c[now]=1
  r.append(now)
if flag==1:
  print(now+1)
else:
  o=[i for i, x in enumerate(r) if x == now]
  print(r[(K-o[0])%(o[1]-o[0])+o[0]]+1)

Submission status: Accepted

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

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

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

tele = [0]
#tele = [0,A[0]-1]
z = 0
s = 0
#B = {0:0,A[0]-1:1}
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])
    z = tele[-1]

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+1)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
A=[i for i in range(1,n+1)]
B=list(map(int,input().split())) 
road=dict(zip(A,B))

#残りi回移動する、移動前に自分がいるところをj
#def walk(i,j):
#        return road[j]
#    else:
#        return walk(i-1,road[j])

j=1
C=[-1 for i in range(n)]
dp=dict(zip(A,C))
dp[1]=0
num=0
while dp[j]!=k-1:
    j=road[j]
    num=num+1
    if dp[j]== -1:
        dp[j]=num
    else:
        t=num-dp[j]
        pre=dp[j]
        itti=j
        break
    if num==k-1:
        print(road[j])
        exit()

mod=(k-pre)%t

for i in range(mod):
    itti=road[itti]
print(itti)

Submission status: Accepted

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

A = [0] + A
visited = [-1] * (N + 1)

pre = 0
cycle = 0

cur = 1
for i in range(N):
    visited[cur] = i

    cur = A[cur]
    if visited[cur] >= 0:
        pre = visited[cur]
        cycle = i + 1 - visited[cur]
        break

cur = 1
for _ in range(min(K, pre + ((K - pre) % cycle))):
    cur = A[cur]

print(cur)

Submission status: Accepted

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

m = {}
for i, a in enumerate(A):
    m[i+1] = a

visited = []
cycle = set()
current_city = 1
visited.append(current_city)
cycle.add(current_city)
cycle_start_index = -1
while 1:
    current_city = m[current_city]
    if current_city in cycle:
        cycle_start_index = visited.index(current_city)
        break
    else:
        visited.append(current_city)
        cycle.add(current_city)

cycle_before = visited[:cycle_start_index]
cycle_after = visited[cycle_start_index:]
if len(cycle_before) - 1 < K:
    print(cycle_after[(K - len(cycle_before)) % len(cycle_after)])
else:
    print(cycle_before[K])

Submission status: Accepted

Solution code:
def main():
  N, K = map(int, input().split())
  A_list = input().split()

  root = [1]

  record = [-1]*N
  break_flag = 0
  for n in range(K):
    new = int(A_list[ int(root[n])-1 ])
    if record[new-1] <0:
      record[new-1]=1
      root.append(new)
    else:
      ind = root.index(new)
      break
  else:
    print(new)
    break_flag = 1
    
  if break_flag == 0:  
	  pre = len(root[:ind])
	  roop = len(root)-pre

	  print(root[ind:][(K-pre)%roop])
   
if __name__ == '__main__':
  main()

Submission status: Accepted

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

s = 1
seen = [False for _ in range(n+1)]
d = []
while not seen[s]:
    seen[s] = True
    d.append(s)
    s = a[s-1]

noncyi = d.index(s)
cyi = len(d) - noncyi
if k < noncyi:
    print(d[k])
else:
    k -= noncyi
    print(d[noncyi + k%cyi])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = []
ord = [-1 for i in range(n+1)]
v = 1
c = 1
l = 0
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:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = [a[i] - 1 for i in range(n)]
    next_i = 0
    seen = [-1] * n
    count = 0
    while True:
        if seen[next_i] != -1:
            start = seen[next_i]
            l = count - seen[next_i]
            break
        seen[next_i] = count
        count += 1
        next_i = a[next_i]
    if k > start:
        k = ((k - start) % l) + start
    for i in range(n):
        if seen[i] == k:
            print(i + 1)
            break


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

visited=[-1]*(n+1)
visited[1]=0

lstart=0
t=0

now=1
while lstart==0:
    if visited[al[now]]<0:
        visited[al[now]]=visited[now]+1
        now=al[now]
        
    else:
        t=visited[now]-visited[al[now]]+1
        lstart=al[now]

if visited[lstart]>=k:
    print(visited.index(k))
            
else:
    print(visited.index(visited[lstart]+(k-visited[lstart])%t))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = []
ord = [-1 for i in range(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:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=2
t=0
path=[]
s=set()
cycle=[]
while(c<=k):
    if a[t] in s:
        #print(path.index(a[t]),a[t])
        cycle=path[path.index(a[t]):]
        k-=c-1
        break
    path.append(a[t])
    s.add(a[t])
    t=a[t]-1
    c+=1
if cycle==[]:
    print(a[t])
else:
    print(cycle[k%len(cycle)])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc167/tasks/abc167_d

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

    c = 1
    while k:
        if k & 1:
            c = a[c]
        na = [0] * (n+1)
        for i in range(n+1):
            na[i] = a[a[i]]
        a = na
        k >>= 1

    print(c)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

dic={}

i=0
dic[1]=i
next_town=1

while True:
    next_town=A[next_town-1]
    K -=1
    i +=1
    if K==0:
        print(next_town)
        break
    elif next_town in dic:
        lp_st=dic[next_town]
        lp_len=i-lp_st

        L=K%lp_len

        if L==0:
            print(next_town)
            break
        else:
            K=L

    else:
        dic[next_town]=i

Submission status: Accepted

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

time=0
color=["white" for _ in range(n+1)]
D=[-1 for _ in range(n+1)]
C,s=[],A[0]
point=0
while 1:
    if color[s]=="white":
        color[s]="gray"
        C.append(s)
        D[s]=time
        time +=1
        s=A[s-1]
    else:
        point=D[s]
        break

loop=C[point:]
if k>len(C):
    k -=point
    print(loop[k%len(loop)-1])
else:print(C[k-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = map(int, input().split())
A = [x-1 for x in A] # 0-indexedに変換

here = 0
visited = set()
route = []

while here not in visited:
    visited.add(here)
    route.append(here)
    here = A[here]

loopStart = route.index(here)

if K <= loopStart:
    ans = route[K]
else:
    lenCycle = len(route) - loopStart
    ans = route[loopStart + (K - loopStart) % lenCycle]

print(ans + 1)

Submission status: Accepted

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

cache={}
log=[]
A = list(map(lambda x:int(x)-1, input().split(' ')))

now=0

while(True):
  log.append(now)
  cache[now]=1
  now=A[now]
  if(cache.get(now)):break

loop_start=log.index(now)
loop_end=len(log)
loop=loop_end-loop_start

if K<len(log):
  print(log[K]+1)
else:
  print(log[(K-loop_start)%loop+loop_start]+1)

Submission status: Accepted

Solution code:
import numpy as np 
from sys import stdin, setrecursionlimit
 

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

t = 1
tpass = [1]
k = 0
j = 1
temp3 = [0]*N
for i in range(N):
    temp = A[t-1] 
    if i == K-1:
        print(temp)
        exit()
    if temp3[temp-1] != 0 :
        idx = tpass.index(temp)
        l = len(tpass)
        j = -1
        break
    else:
        
        t = temp
        temp3[t-1] = 1
        tpass.append(temp)
        k += 1

try:
    a = K - k
    loop = l - idx
    b = a % loop 
    temp2 = tpass[idx:]
    ans = temp2[b-1]
    print(ans)
except:
    pass

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
d2 = []
hist=[-1]*(n+1)
hist[0] = 0
cur = 1
d2.append(1)
st_idx = 0
rp_lgt = 1
for i in range(n):
  cur = a[cur-1]
  if hist[cur-1] >= 0 :
     d2.append(cur)
     st_idx = hist[cur-1]
     rp_lgt = i - st_idx + 1 
     break
  else:
    d2.append(cur)
    hist[cur-1] = i + 1
wk = k - st_idx
md = wk % rp_lgt
if k < st_idx:
  ans = d2[k]
else:
  ans = d2[md+st_idx]
print(ans)

Submission status: Accepted

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

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

    count = 1
    now = 0
    visited = [1]
    set_v = set()
    set_v.add(1)
    l = -1
    while count < N:
        x = A[now]
        if x in set_v:
            l = visited.index(x)
            break
        else:
            count += 1
            visited.append(x)
            set_v.add(x)
            now = x-1
    r = count
    # print(l,r,visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])

if __name__ == '__main__':
    main()

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
q=True
v=True
cnt=0

while q:
    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)
        v=not v
        break
    if cnt==10**7:
        q=not q
if v:
    loop_len=cnt-loop
    q=True
    k=(k-loop)%loop_len
    cnt=0
    if k==0:
        print(pl)
    else:
        while q:
            cnt+=1
            pl=a[pl-1]
            if cnt==k:
                print(pl)
                break
            if cnt==10**7:
                q=not q

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections


# 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 = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    cur = 1
    c = {}
    route = []
    roop = None
    while (True):
        if cur in c:
            roop = cur
            break
        route.append(cur)
        c[cur] = 1
        cur = A[cur - 1]
    idx = route.index(roop)
    if K <= idx:
        print(route[K])
        return
    # route = route[idx:]
    print(route[(K - idx) % (len(route) - idx) + idx])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,k=map(int, input().split())

A = deque(map(int, input().split()))
li = []
li2 = [0]*n
li.append(1)

next = 0

t=0
rep = False

for i in range(k):
    if i == k:
        print(next+1)
        exit()

    if li2[next] == 1:
        t = li.index(next+1)
        rep = True
        li.pop()
        break

    li.append(A[next])
    li2[next] = 1
    next = A[next]-1


tmp = (k-t)%len(li[t:])
print(li[tmp+t])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    visited = {i:0 for i in range(N)}
    visited[0] = 1
    count = 0
    pre_count = 0
    cicle_idx = 0
    is_cicle = False
    idx = 0
    ans = -1
    while not is_cicle:
        count += 1
        if count == K:
            ans = A[idx]
        idx = A[idx]-1
        if visited[idx] == 1:
            visited[idx] = 2
            is_cicle = True
            cicle_idx = idx
            break
        visited[idx] = 1
    if ans == -1:
        cicle = []
        will_push = False
        while True:
            idx = A[idx]-1
            if idx == cicle_idx:will_push = True
            if len(cicle) > 0 and visited[idx] == 2:break
            if will_push:
                cicle.append(idx)
        pre_count = count - len(cicle)
        ans_idx = (K - pre_count) % len(cicle)
        print(cicle[ans_idx]+1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

now = 1
check = [-1]*(n+1)

for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now]
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop) + afterloop))
    exit()
print(now)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a = 0
t = 1
d = 0
hoge_list = []
visit = [False for _ in range(n+1)]
while a < k:
  hoge_list.append(t)
  t = a_list[t-1]
  a += 1
  if visit[t]:
    b = hoge_list.index(t)
    d += 1
    break
  visit[t]=True
if d == 0:
  print(t)
else:
  e = (k-b)%(a-b)
  print(hoge_list[b+e])

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    N, K = map(int, input().split())
    *A, = (int(x) - 1 for x in input().split())

    rs = [-1] * N

    def dfs(cur=0, rest=K):
        if ~rs[cur]:
            loop_range = rs[cur] - rest
            rest %= loop_range

        if rest == 0:
            return cur + 1  # -> 1-ind

        rs[cur] = rest
        return dfs(A[cur], rest - 1)

    print(dfs())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1]
for i in range(n):  
    l.append(a[l[i]-1])
    
p = l.index(l[-1])
if k<=n:
  print(l[k])
  exit()
  
x = (k-n+1)%(n-p)
if x==0:
  print(l[n-1])
else:
  print(l[x+p-1])

Submission status: Accepted

Solution code:
import numpy as np 
from sys import stdin, setrecursionlimit
 
setrecursionlimit(10 ** 9)

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

t = 1
tpass = [1]
k = 0
j = 1
temp3 = [0]*N
for i in range(N):
    temp = A[t-1] 
    if i == K-1:
        print(temp)
        exit()
    if temp3[temp-1] != 0 :
        idx = tpass.index(temp)
        l = len(tpass)
        j = -1
        break
    else:
        
        t = temp
        temp3[t-1] = 1
        tpass.append(temp)
        k += 1

try:
    a = K - k
    loop = l - idx
    b = a % loop 
    temp2 = tpass[idx:]
    ans = temp2[b-1]
    print(ans)
except:
    pass

Submission status: Accepted

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

a = [0] + list(map(int, input().split()))
a1 = [0] * (n+1)

step = 1
start = 0
while(True):
    start += 1
    a1[step] += 1
    step = a[step]
    if a1[step] == 1:
        break
c = step
gap = 0
while(True):
    gap += 1
    step = a[step]
    if step == c:
        break
result = 1
if k > start:
    k = (k-start) % gap
    result = c
for _ in range(k):
    result = a[result]

print(result)

Submission status: Accepted

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

d=set()
e=[]
mir=1
while 1:
  if mir in d:
    g=e.index(mir)
    f=e[g:]
    e=e[:g]
    break
  else:
    d.add(mir)
    e.append(mir)
    mir=c[mir]
if b<len(e):
  print(e[b])
else:
  b=b-len(e)
  print(f[b%(len(f))])

Submission status: Accepted

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

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

L = []
L.append(1)
f = 1
memo = [-1] * N
memo[0] = 0
cnt = 1

while 1:
    L.append(A[f-1])
    f = A[f-1]
    if memo[f-1] != -1:
        loop = cnt - memo[f-1]
        break
    memo[f-1] = cnt
    cnt += 1

#print(L)
#print(loop)
NL = L[-(loop+1):-1]
#print(NL)

if K <= (len(L) - 1) - loop:
    print(L[K])
else:
    K -= (len(L) - 1) - loop
    a = K % len(NL)
    print(NL[a])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
list1 = list(map(int,input().split()))
visited_town = [[] for i in range(N+1)] #どの町にいつ訪れたか,配列の0あける。
visited_time = [None for i in range(2*N)] #訪れた町の時系列。こっちは0あけない。

visited_town[1].append(0) 
visited_time[0] = 1

cycle_start = -1
cycle_end = -1

for i in range(1,2*N):
  next_town = list1[visited_time[i-1]-1]
  visited_town[next_town].append(i)
  visited_time[i] = next_town
  if len(visited_town[next_town]) == 2:
    cycle_start = visited_town[next_town][0]
    cycle_end   = visited_town[next_town][1]
    break

if K < cycle_start:
  ans = visited_time[K]
  print(ans)
else :   
  syuuki = cycle_end-cycle_start
  cycle = visited_time[cycle_start:cycle_end]
  ans = cycle[(K-cycle_start) % syuuki]
  print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
def get_cycle_length():
  pointer1 = 1
  pointer2 = a[1-1]
  while pointer1 != pointer2:
    pointer2 = a[pointer2-1]
    pointer2 = a[pointer2-1]
    pointer1 = a[pointer1-1]
  cycle_length = 1
  pointer2 = a[pointer2-1]
  while pointer1 != pointer2:
    pointer2 = a[pointer2-1]
    cycle_length += 1
  return cycle_length
def get_start_length(cycle_length):
  pointer1 = 1
  pointer2 = 1
  for _ in range(cycle_length):
    pointer2 = a[pointer2-1]
  start_length = 0
  while pointer1 != pointer2:
    start_length += 1
    pointer1 = a[pointer1-1]
    pointer2 = a[pointer2-1]
  return start_length
if k>n:
  cycle_length = get_cycle_length()
  start_length = get_start_length(cycle_length)
  remainder_steps = k - start_length
  modded_remainder = remainder_steps % cycle_length
  k = start_length + modded_remainder
town = 1
for _ in range(k):
  town = a[town-1]
print(town)