Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n,k=MI()
    a = LI()
    b = [0]*n
    for i in range(n):
        b[i]=a[i]-1
    # x = k%n
    # print(x)
    prev = 0
    d = dict()
    l = []
    while prev not in d:
        d[prev]=1
        l.append(prev)
        prev=b[prev]
    # print(prev,"t")
    s=-1
    for i in range(len(l)):
        # print(l[i])
        if l[i]==prev:
            s=i
    # print(s,"st")
    md = (k-s)%(len(l)-s)
    print(l[s+md]+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
log = []
visited = [False for i in range(n)]
now = a[0]-1
loop = False
for i in range(k):
    if visited[now] == True:
        loop = True
        num = i
        break
    log.append(now)
    visited[now] = True
    now = a[now]-1
else:
    print(now+1)
if loop:
    for i in range(len(log)):
        if log[i] == now:
            log_list = log[i:]
            loop_num = len(log_list)
            break
    k -= (num)
    k %= loop_num
    print(log_list[k-1]+1)

Submission status: Wrong Answer

Solution code:

#import numpy as np
from functools import *
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))




def search(x,step,vnode):
    global L,visited
    
    #print(visited,x)
    visited[x]=step
    vnode.append(x)
    if visited[L[x]]>=0:
        C=step+1-visited[L[x]]
        k=(K%(2*C)-visited[L[x]])%C
        
        #print(k)
        #print(vnode)
        #print(k,L[x],visited[L[x]])
        vnode.append(L[x])
        print(vnode[visited[L[x]]+k])
               
        #print(step,x,visited)
        sys.exit(0)
        return
    
    
    search(L[x],step+1,vnode)
    
    
    

N,K=acinput()
L=[0]
L.extend(acinput())

visited=[-1]*(N+1)
#visited[1]=1
search(1,0,[])

Submission status: Wrong Answer

Solution code:
import sys
# sys.stdin=open("input1.in","r")
# sys.stdout=open("outpul.out","w")
input=sys.stdin.readline
from collections import defaultdict
N,K=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,-1)
path=[1]
ind=0
count=0
x=1
t=-1
flag=False
Hash=defaultdict(lambda:0)
for i in range(N+1):
    ne=L[x]
    if Hash[ne]:
        flag=True
        t=Hash[ne]
        break
    path.append(ne)
    ind+=1
    Hash[ne]=ind
    x=ne
if flag==True:
    loop=path[t::]
    if K<=(len(path)):
        print(path[K-1])
    else:
        K=K-len(path)
        K=K%len(loop)
        print(loop[K])
else:
    print(path[K-1])

Submission status: Wrong Answer

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

dic = dict()
for i in range(n):
    dic[i+1] = p[i]


keynum = 0
log = [1]
next = dic[1]
log.append(next)
k -= 1
while k:
    next = dic[next]
    if next in log:
        keynum = log.index(next)
        k -= 1
        break
    log.append(next)
    k -= 1
looplen = len(log[keynum:])
res = k%looplen
print(log[keynum+res])

Submission status: Wrong Answer

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input = sys.stdin.readline
    n,k=L()
    a=L()
    visited=[0]*(n+1)
    tmp=0
    now=0
    visited[0]=1
    loopat=0
    for i in range(k):
        #print(visited,end="")
        tmp=i+2
        now=a[now]-1
        #print(now)
        #print(tmp,now+1)
        if visited[now]==0:
            visited[now]=i+2
        else:
            loopat=now
            break
    #print(visited)
    #print(loopat,visited[loopat],tmp)
    #print(tmp,now)
    if tmp-visited[loopat]==0:
        tmp2=k
        dist=1
        now=0
    else:
        tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
        dist=loopat+1
    #print(tmp2)
    
    #print(now,dist)
    #print(now+1,end=" ")
    for i in range(tmp2):
        now=a[now]-1
        dist=now+1
        #print(now,dist)
    #print()
    print(dist)
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(j) for j in input().split()]
dp = [0] * (n + 1)
start = 0
for i in range(1, n + 1):
    dp[i] = a[dp[i - 1]] - 1
b = dp[n]
if k < n:
    print(dp[k] + 1)
else:
    for j in range(n - 2, -1, -1):
        if dp[j] == b:
            period = n - j
            break
    for i in range(n - 1 - period):
        if a[i] == a[i + period]:
            start = i
            break
    k = start + (k - start) % period
    print(dp[k] + 1)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int, input().split()))
a=list(map(int, input().split()))
b=[0]*(n+1)
for i in range (n):
    b[i+1]=a[i]
ctr=[0]*(n+1)
x=1
c=0
s=0
while c==0:
    y=b[x]
    s+=1
    if ctr[y]==0 and y!=1:
        ctr[y]+=s
        x=y
    else:
        ll=s-ctr[y]
        c+=1
        f=ctr[y]
if k<=f:
    ans=ctr.index(k)
else:
    zz=(k-f)%ll
    ans=ctr.index(zz+f)
print(ans)

Submission status: Wrong Answer

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

  count=0
  now_point = 1
  root_list = [a_list[0]]
  while True:
    now_point = a_list[now_point - 1]
    count += 1
    if a_list[now_point - 1] in root_list:
      loop_list = root_list[root_list.index(a_list[now_point - 1]):]
      first_num = len(root_list[:root_list.index(a_list[now_point - 1])])
      loop_num = len(loop_list)
      break
    else:
      root_list.append(a_list[now_point - 1])

  now_point = 1
  l = (k-first_num) % loop_num
  for i in range(first_num+l):
        now_point = a_list[now_point - 1]

  print(now_point)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

ans = A[0]

d = {0:1, ans -1:1}
#移動する可能性がある街の個数uを出す
for i in range(N):
  #print(ans)
  ans = A[ans - 1]
  if ans -1 not in d:
    d[ans -1] = 1
  else:
    d[ans - 1] += 1
  
#print("d", d, len(d))
u = len(d)

if d[0] == 1:
  a = (K - 1) % (u - 1)
else:
  a = K % u
if a == 0:
  a = u

#print("a", a)
ans = A[A[0] - 1]
for i in range(a + 1):
  #print(i, ans)
  ans = A[ans - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[]
count=0
i=0
for n in range(10**7):
    if A[i] in l:
        count=l.index(A[i])
        break
    else:
        l.append(A[i])
        i=A[i]-1
        
print(A[(K-count)%(n)])

Submission status: Wrong Answer

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

idx = (k%n)-1
print(A[A[idx]-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def get_int():
    return int(input())


def get_tuple():
    return map(int, input().strip().split())


def get_ls():
    return list(map(int, input().strip().split()))


n, k = get_tuple()
ls = get_ls()
visited = defaultdict(int)
times = 0
town = 1
while town not in visited:
    visited[town] = times
    times += 1
    town = ls[town - 1]

period = times - visited[town]
iter_req = visited[town]
k -= visited[town]
#print(period)
if k > period:
    k %= period
iter_req += k
#print("Starting town is ",town)
#print("iter_req is",iter_req)
town = 1
ans = ls[town-1]
while iter_req >1:
        town = ans
        ans = ls[town - 1]
        k -= 1
        #print(ans)
        iter_req -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lst = [int(i) for i in input().split()]
if k > n:
    k = n + k%n

count = 0
i = 1
while count < k:
    town = lst[i-1]
    i = town
    count += 1
print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [0]*n
done[A[0]] = 1
arrive_time[A[0]] = time
last = 0
while True:
    v = A[0]
    if done[A[v]] == 0:
        done[A[v]] = 1 
        time += 1
        arrive_time[A[v]] = time
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)

Submission status: Wrong Answer

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

count = 0
t= 0

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

print(t+1)

Submission status: Wrong Answer

Solution code:
# D

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

def compute(city, K):
    for i in range(K):
        # print('\t', city)
        city = As[city-1]
    print(city)


if N > K:
    compute(1, K)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}

while not cities_visited[city - 1]:
    # print(city)
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    city = As[city-1]
    i += 1

loop_start = city_visited_time[city-1]
loop_end = i

div = (K - loop_start) // (loop_end - loop_start + 1)
# print(loop_start, loop_end, div, K % (loop_end - loop_start + 1))
compute(city, K % (loop_end - loop_start + 1) + loop_start + 1)

Submission status: Wrong Answer

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

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

count = 0
start = a[0]

while(count <= K):
    now = a[start-1]
    next = a[now-1]
    start = next
    count += 1

print(a[now-1])

Submission status: Wrong Answer

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

  history = []
  current = 0
  while True:
    history.append(current)
    current = A[current]
    if current in history:
      loop_length = len(history[history.index(current):] )
      length_to_loop = len(history[:history.index(current)])
      additional_way = (K-length_to_loop)%loop_length
      print(A[length_to_loop + additional_way] + 1)
      return True

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A_li = list(map(int,input().split()))
junban = [1,]
idx = 0
flag = False
flag2 = False
while True:
    tmp = A_li[idx]
    if tmp in junban:
        if flag:
            flag = True
        else:
            flag2 = True
    junban.append(tmp)
    idx = tmp - 1
    if flag2:
        break
#print(junban)
syuuki = []
check = [0]*N
for i in junban[::-1]:
    syuuki.append(i)
    if check[i-1]:
        break
    check[i-1] = 1
syuuki = syuuki[::-1][:-1]
#print(syuuki)
saisyo = 0
a = len(syuuki)
for i in range(len(junban)):
    if junban[i:i+a] == syuuki:
        saisyo = i
        break
#print(saisyo)
indekkusu = (K-saisyo)%len(syuuki)
print(syuuki[indekkusu])

Submission status: Wrong Answer

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

#ループする場合
flag=[0]*N
patt=[]
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1

srt = patt.index(patt[-1])
#print(srt)
end = len(patt)-2
ptrn = patt[srt:end+1]

B = (K-srt) % len(ptrn)
if B==0:
    print(ptrn[0]+1)
else:
    print(ptrn[B]+2)
    #print('0000000')

Submission status: Wrong Answer

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

i = 0
lp = 0
step = []
while visited[i] == 0:
  if lp == k - 1:
    exit()
  visited[i] = 1
  next_visit = A[i] 
  step.append(i)
  lp += 1
  i = next_visit

lp_start = step.index(i)
syuki = lp - lp_start

if lp_start > k:
  ans = step[k]
else:
  cnt = (k - lp_start) % syuki
  ans = step[lp_start:][cnt] + 1

print(ans)

Submission status: Wrong Answer

Solution code:

n,k = map(int,input().split())
A = list(map(int,input().split()))
ex = [0]*n
now = 1
if k == 0 :
    print(A[0])
for i in range(k) :
    if i == k-1 :
        print(now)
        exit()
    elif ex[now-1] == 0 :
        ex[now-1] = i+1
        now = A[now-1]
    else :
        J = (k-i)%(i-ex[now-1]+1)
        for j in range(J) :
            now = A[now-1]
        print(now)
        exit()

Submission status: Wrong Answer

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

li = [0]
li.extend(list(map(int, input().split())))

def search(town, li, times):
  if times == 0:
    return town
  return search(li[town], li, times-1)

tuita = [0]*(n+1)
cnt = 0
town = 1

while True:
  town = li[town]
  cnt += 1
  if tuita[town] == 0:
    tuita[town] = cnt
  else:
    if k < tuita[town]:
      break
      print(search(1, li, k))
    elif k == tuita[town]:
      break
      print(town)
    else:
      break
      print(search(town, li, (k - tuita[town]) % (cnt - tuita[town])))
    break

Submission status: Wrong Answer

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

loop_count = 0
loop = [0] * N
i = 1
town = A[0] - 1
loop[0] = i
while True:
    if loop[town] == 0:
        i += 1
        loop[town] = i
        town = A[town] - 1
    else:
        break
loop_size = i - loop[town] + 1

if loop_size != 0:
    K = (K - i) % loop_size

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

print(town + 1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a]
visited = [False]*n
route = []
now = 0
hop = 0
while visited[now]==False:
    visited[now]=True
    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:]
f = True
if k-1 < loop_st:
    print(route[k])
else:
    k-=loop_st
    print(loop[k%len(loop)]+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
ordi = [0, ]
for i in range(n):
    if a[ordi[-1]] - 1 not in ordi:
        ordi.append(a[ordi[-1]] - 1)
    else:
        ordi.append(a[ordi[-1]] - 1)
        index = ordi.index(a[ordi[-1]] - 1)
        len_ = len(ordi) - index
        break
print(ordi[index + (k - index) % len_])

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [0]*n
done[A[0]] = 1
arrive_time[A[0]] = time
last = 0
while True:
    v = A[0]
    if done[A[v]] == 0:
        done[A[v]] = 1 
        time += 1
        arrive_time[A[v]] = time
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)

print(arrive_time)

Submission status: Wrong Answer

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

first = {}
first[1] = 0
second = {}
flag = 1
i = 0
warp = 0
while flag:
    warp += 1
    if A[i] in first.keys():
        second[A[i]] = warp
        flag = 0
        break
    first[A[i]] = warp
    i = A[i] - 1

loop_town = []
stand = 0
loop = 0
for key, value in second.items():
    stand = first[key]
    loop = value - first[key]
    for key2, value2 in first.items():
        if first[key] <= value2 < value:
            loop_town.append(key2) 

if loop == 0:
    if K <= N:
        print(A[K-1])
    else:
        print(A[N-1])
else:
    print(loop_town[(K-stand)%loop])

Submission status: Wrong Answer

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [a - 1 for a in A]
    L = [0]
    s = 0
    c = 0
    T = 0
    for i in range(N):
        t = A[s]
        j = bisect.bisect_left(L, t)
        if j < len(L):
            if t == L[j]:
                T = t
                break
        L.insert(j, t)
        s = t
    s = 0
    I = 0
    for i in range(N):
        if T == s:
            I = i
            break
        t = A[s]
        s = t
    C = len(L) - I
    s = 0
    for k in range((K-I)%C+I):
        t = A[s]
        s = t
    print(s+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count = 0
cur = 0
for _ in range(N):
    count += 1
    cur = A[cur]
    if cur == 0:
        break

C = K%count
cur = 0
for _ in range(C):
    cur = A[cur]
print(cur+1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
s=1
B=[1]
for i in range(K):
  s=A[s-1]
  if s in B:
    u=B.index(s)
    u_=len(B)-u#周期の長さ
    t=(K-u+1)%u_
    if t>=1 and u>=1:
      print(B[u+t-1])
      exit()
    elif u==0:
      t=(K+1)%u_
      print(B[t-1])
      exit()
    else:
      print(B[u])
      exit()
  else:
    B.append(s)
 
print(s)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n,k = mp()
x = ip()
if x[0] == 1:
    print(1)
    exit()
cyc = [1]
vis = {}
i = 1
while not vis.get(i,0):
    vis[i] = 1
    i = x[i-1]
    cyc.append(i)
#print(cyc)
if k <= len(cyc):
    print(cyc[k-1])
    exit()
last = cyc[-1]
kk = cyc.index(last)
k -= kk
ind = (k-1) % (len(cyc)-kk-1) + 1
print(cyc[kk+ind-1])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
cycle=[0]
s_cyc=set()
s_cyc.add(0)
flag=0
id=0
for i in range(N):
    a[i]-=1
while N>0:
    if a[id] in s_cyc:
        node=cycle.index(a[id])
        break
    else:
        cycle.append(a[id])
        s_cyc.add(a[id])
        id=a[id]
    N-=1
if N==0:
    print(a[id]+1)
else:
    K-=node
    cycle=cycle[node::]
    q=K%len(cycle)
    print(cycle[q]+1)

Submission status: Wrong Answer

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


a = list(map(int,input().split()))
b = [0 for i in range(2*10**5)]
l = []
x = 1

if k <= 2*10**5:
    for i in range(k-1):
        x = a[x-1]
    
if k <= 2*10**5:    
    print(x)
    exit()


for i in range(2*10**5):
    if b[x] == 0:
        b[x] += 1
    else:
        res = x+1
        break
    
    l.append(x+1)
    x = a[x]-1




roup = l[l.index(res):]

k -= (len(l)-len(roup))

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
nums = {0:1}
cnt_one = 0
cnt_two = 0
pos = a[0] - 1
num_list = [0]
while(True):
    if pos not in nums:
        nums[pos] = 1
        num_list.append(pos)
    else:
        nums[pos] += 1
        if nums[pos] == 3:
            nums[pos] -= 1
            break
    pos = a[pos] - 1
for key, value in nums.items():
    if value == 1:
        cnt_one += 1
        num_list.remove(key)
    else:
        cnt_two += 1
pos_ans = (k - cnt_one) % cnt_two
ans = num_list[pos_ans] + 1
print(ans)

Submission status: Wrong Answer

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

visit = [0 for _ in range(n)]




i = 0
v = 0
while True:
    i+=1
    if visit[v]==0:
        visit[v]=i
        v = A[v]-1
        
    else:
        len_roop = i - visit[v]
        break

flag = 0
for i in range(n):
    if visit[i] == k+1:
        flag =1
        ans = i
    
if flag:
    print(ans+1)

else:
    temp_tel = visit[v]-1
    amari = (k-temp_tel)% len_roop
    ans = v
    for i in range(amari):
        ans = A[ans-1]
    print(ans+1)

Submission status: Wrong Answer

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

exist = [1]
#exist.append(a[0])
ex = {}
ex[1] = 0
#ex[a[0]] = 0

cnt = 1
while(True):
    if a[exist[-1]-1] in ex:        
        idx = exist.index(a[exist[-1]-1])
        exist.append(a[exist[-1]-1])
        break
    ex[a[exist[-1]-1]] = 0
    exist.append(a[exist[-1]-1])
    
    cnt += 1
    if cnt >= k-1:
        print(exist[-2])
        exit()


#k = k-idx
d = (k-idx) % (cnt-idx)

print(exist[d+idx])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().strip()

def main():
    N,K = map(int,input().split())
    A_list = list(map(int,input().split()))
    A_narabikae_list = [1]
    A_kako = [1]
    rep_idx = 0
    idx = 1-1
    for ai in A_list:
        A_narabikae_list.append(A_list[idx])
        if A_list[idx] in A_kako:
            rep_start = A_narabikae_list.index(A_list[idx])
            A_kako = A_kako[rep_start::]
            rep_end = rep_start + len(A_kako) -1
            break
        A_kako.append(A_list[idx])
        idx = A_list[idx]-1
    A_kako_idx = (K-rep_start)%(rep_end-rep_start+1)
    print(A_kako[A_kako_idx])

main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
visited = [0]*(n+1)
turn = [0]*(n+1)
visited[1] = 0
nxt = 1
i = 1
while True:
  if visited[a[nxt]]:
    nxt2 = a[nxt]
    break
  turn[a[nxt]] = i
  visited[nxt] = 1
  i += 1
  nxt = a[nxt]



loop = i-turn[nxt2]
if turn[nxt2] == 0:
  loop = i
  start = 0
start = turn[nxt2]
#print(turn,i,visited)
#print(start,loop)
if start == 0 and k % loop == 0:
  print(1)
  quit()

Submission status: Wrong Answer

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

now = A[now-1]
route = [now]
count += 1

def check(now, route, count):
  now = A[now-1]
  if now in route:
    return 0
  else:
    route.append(now)
    count += 1

check(now, route, count)

print(route[(K % count)-1])

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, K = mulinputs()
    datas = list(mulinputs())

    # idx = 0
    # next = 1
    # dones = [False] * N
    # dones[0] = True
    # while idx < K:
    #     if dones[next-1]:
    #         break
    #     dones[next-1] = True
    #     next = datas[next-1]
    #     idx += 1
    # loop_cnt = idx + 1
    idx = 0
    next = 1
    dones = [0] * N
    while idx < N*2:
        dones[next-1] += 1
        next = datas[next-1]
        idx += 1
    z_cnt = len(list(filter(lambda x: x == 0, dones)))
    mono_cnt = len(list(filter(lambda x: x == 1, dones)))
    if K <= z_cnt + mono_cnt:
        idx = 0
        next = 1
        while idx < K:
            next = datas[next-1]
            idx += 1
        print(next)
        exit()

    loop_cnt = len(list(filter(lambda x: x > 1, dones)))
    loop = []
    for idx, elm in enumerate(datas):
        if dones[idx] <= 1:
            continue
        loop.append(elm)
    idx = (K%loop_cnt)-1
    if idx < 0:
        idx = loop_cnt -1
    print(loop[idx])
    # _k = int(K - (K // loop_cnt) * loop_cnt)
    # idx = 0
    # next = 1
    # while idx < _k:
    #     next = datas[next-1]
    #     idx += 1

    # # 出力
    # print(next)

Submission status: Wrong Answer

Solution code:
a = raw_input().split()
n = int(a[0])
k = int(a[1])
a = raw_input().split()
m = []
i = 0
while 1:
    if i in m:
        break
    m.append(i)
    i = int(a[i]) - 1
l = len(m)
s = m.index(i)
res = (k - s) % (l - s)
print m[res + s] + 1

Submission status: Wrong Answer

Solution code:
def teleport(k, a):
    l = [1]
    b = a[0]
    flag = True
    while flag:
        # print(b)
        if a[b-1] in l:
            flag = False
            l.append(b)
        else:
            l.append(b)
            b = a[b-1]
            
    # print(l)
    r = l.index(a[b-1])
    # print(r)
    new_l = l[r:]
    # print(new_l)
    print(new_l[(k+1-r)%(len(l)-r)-1])
    # print(l[(k+1)%len(l)-1])

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
teleport(k, a)

Submission status: Wrong Answer

Solution code:
def detectCycle(x, a):
    start,length = 0, 1
    p1, p2 = a[x], a[a[x]]
    while p1 != p2:
        p1, p2 = a[p1], a[a[p2]]

    p2 = x
    while p1 != p2:
        p1, p2 = a[p1], a[p2]
        start += 1

    p2 = a[p1]
    while p1 != p2:
        p2 = a[p2]
        length += 1
    
    return start,length

n, k = (int(x) for x in input().split())
a = [-1] + [int(x) for x in input().split()]
start, length = detectCycle(1,a)

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

k %= length
for i in range(k):
    loc = a[loc]
print(loc)

Submission status: Wrong Answer

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

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

city = 1
route = []
route.append(0)

while True:
    city = roads[city-1] 
    if city in route:
        st = route.index(city)
        length = len(route) - st
        break
    route.append(city)


cnt = (k+1-st) % length


print(route[cnt+st-1])