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:
from collections import deque
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]
    pos = 1
    a = [False] * N
    a[0] = True
    tmp = deque([pos])
    for _ in range(K):
        pos = As[pos - 1]
        if a[pos - 1]:
            idx_s = tmp.index(pos)
            break
        a[pos - 1] = True
        tmp.append(pos)
    else:
        print(list(tmp)[-1])
        return

    K = K - idx_s
    tmp = list(tmp)
    print(tmp[idx_s:][K % (len(tmp) - idx_s)])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = input().split()
A_MAP = {}
for i in range(N):
    A_MAP[str(i+1)] = A[i]

route_hash = {'1': 0}
current_pos = '1'
next_pos = ''
counter = 0
breaked = False
while counter < K:
    next_pos = A_MAP[current_pos]
    counter+=1
    if next_pos in route_hash:
        breaked = True
        break
    route_hash[next_pos] = counter # たどり着くまでにかかった回数
    current_pos = next_pos

if not breaked:
    print(current_pos)
    exit()

remain = K - counter
counter -= route_hash[next_pos]
remain = remain % counter

current_pos = next_pos
for i in range(remain):
    next_pos = A_MAP[current_pos]
    route_hash[next_pos] = counter # たどり着くまでにかかった回数
    current_pos = next_pos
print(current_pos)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))
iti=1
count=0
sokuseki=[0]*n
while True:
    iti=a[iti-1]
    count+=1
    if sokuseki[iti-1]:
        m,r=divmod(k-count,count-sokuseki[iti-1])
        count+=(count-sokuseki[iti-1])*m
    sokuseki[iti-1]+=count
    if count==k:
        print(iti)
        exit()

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split(' ')]
a_s = [int(i) - 1 for i in input().split(' ')]

to = 0
to_s = []
m = {}
count = 0
while True:
  count += 1
  m[to] = count
  to_s.append(to)
  #print("#",to)
  #次の町に行く
  to = a_s[to]

  #すでに行ったことがあれば抜ける
  if to in m:
    break

#ループに入るまでの工程数
p1 = m[to] - 1
#ループの周期
p2 = count - p1

#print(to_s, m, p1, p2)
if k <= p1:
  ans = to_s[k]
else:
  pos = (k - p1) % p2 + p1
  #print(pos)
  ans = to_s[pos]
#print(ans + 1, p1,  p2)
print(ans + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
memo=[-1]*(N+1)
x=1
begin=-1
loop=[]
for i in range(1,K+1):
    if memo[x] == -1:
        loop.append(x)
        memo[x]=i
        x=A[x-1]
        
    else:
        begin=memo[x]
        stop=i-1
        break
# print('begin', begin)
# print('stop', stop)
loop=loop[begin-1:]



if begin == -1:
    print(x)
else:
    print(loop[(K-begin+1)%(stop-begin+1)])

Submission status: Accepted

Solution code:
class Telp:
    def __init__(self, to, idx):
        self.to = to
        self.idx = idx
        self.visited = False
        self.step = -1

    def visit(self, step):
        self.visited = True
        self.step = step

    def is_visited(self):
        return self.visited


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

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

net = {}

for i in range(n):
    net[i] = Telp(a[i], i)

current = net[0]
count = 0
path = []

while not current.visited:
    # print(current.to)
    path.append(current)
    current.visit(count)
    current = net[current.to - 1]
    count += 1
    if count == k:
        print(path[-1].to)
        exit(0)
    # print("count", count)

offset = current.step
loop = count - offset
fact_idx = (k - offset) % loop

# print("count, offset, loop, fact_idx", count, offset, loop, fact_idx)
# print("ans", path[offset + fact_idx - 1].to)

print(path[offset + fact_idx - 1].to)

Submission status: Accepted

Solution code:
def main():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  flag = [False] * N
  flag[0] = True
  move = [0]
  num = 0
  while True:
    num += 1
    c_next =  A[move[-1]]-1
    move.append(c_next)
    if flag[c_next]:
      break
    else:
      flag[c_next] = True
  for i, j in enumerate(move):
    if j == c_next:
      if c_next == 0:
        key = 0
      else:
        key = i
      c_cycle = num-key
      break
  if K < key:
    print(move[K]+1)
  else:
    K -= key
    K %= c_cycle
    print(move[key + K]+1)

if __name__  == "__main__":
  main()

Submission status: Accepted

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

T = defaultdict(int)

key_town = 0
count = 0

if K < 3 * (10 ** 5):
    ans = 1
    for k in range(K):
        ans = A[ans]
    print(ans)
    sys.exit(0)


T[1] = 1

now = 1
for i in range(1, len(A)):
    now = A[now]
    if T[now] == 0:
        T[now] = i + 1
    else:
        key_town = now
        count = i - T[now] + 1
        break

if count == 0:
    print(key_town)
    sys.exit(0)

k = (K - T[key_town]+1) % count

ans = key_town
for i in range(k):
    ans = A[ans]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    n = [-1] * (N + 1) # 各町を何番目に通ったか
    
    i = 1
    cur_town = 1
    next_town = A[cur_town-1]
    while i <= K:
        cur_town = next_town
        # 次の町がまだ訪れたことのない町なら次の町へ
        if n[A[cur_town-1]] == -1:
            n[cur_town] = i
            next_town = A[cur_town-1]
            i += 1
        # ある場合
        else:
            # ループの長さ
            loop_len = i - n[A[cur_town-1]] + 1
            # 残り
            rest = K - i
            # print(n)
            # print(i, loop_len, rest, A[cur_town-1], n[A[cur_town-1]])
            if rest >= loop_len:
                n[cur_town] = i
                i += loop_len * int(rest // loop_len)
            else:
                next_town = A[cur_town-1]
                i += 1
    print(cur_town)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

arr = [1]
cnt = 1
b = 10 ** 7
ans = [0 for i in range(N+1)]

for i in range(N):
  if i == 0:
    ans[1] += 1
    s = List[i]
    arr.append(s)    
  else:
    if ans[s] == 1:
      b = arr.index(List[s-1])
      break
    else:
      ans[s] += 1
      s = List[s-1]
      arr.append(s)
            
l = len(arr)
c = int( (K-b) % (l-b) )

if K-b > 0:
  print(arr[b+c])
elif K-b == 0:
  print(arr[b])
else:
  print(arr[K])

Submission status: Accepted

Solution code:
data = input().rstrip().split(" ")
tele = input().rstrip().split(" ")
telepo = [int(i) for i in tele]

max = int(data[1])
limit = max
times = 0
pos = 1
experience = [1]
check = {1}
before = 0
while max > 0:
    pos = telepo[pos - 1]
    max -= 1
    times += 1
    before = len(check)
    check.add(pos)
    if before == len(check):
        length = len(experience) - experience.index(pos)
        max = max % length
        if max == 0:
            break
        while max > 0:
            pos = telepo[pos - 1]
            max -= 1
            times += 1
            #print(pos)
        break
    experience.append(pos)
print(pos)

Submission status: Accepted

Solution code:
import copy

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

ref = [False] * (n + 1)
cyc = False
cyc_num = -1

idx = 0
path = []

while True:
    if ref[idx + 1] == True:
        cyc_num = idx + 1
        break

    cur = nums[idx]
    ref[idx + 1] = True
    path += [idx + 1]
    idx = cur - 1

prev = len(path)

# print('Cyc', cyc_num)
# print('path 1:', ' '.join(list(map(str, path))))

from_idx = 0
for p in path:
    if p == cyc_num:
        break
    else:
        from_idx += 1

new_path = copy.deepcopy(path[from_idx:])

#print('path 2:', ' '.join(list(map(str, new_path))))

start = len(path) - len(new_path)

if k <= start:
    idx = 0

    for i in range(k):
        cur = nums[idx]
        idx = cur - 1

    print(idx + 1)
else:
    k -= start
    k %= len(new_path)

    print(new_path[k])


"""
5 2
2 3 4 5 3
"""

Submission status: Accepted

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

mod_max = n
rep_start = n
cur = 1
flag = 0
for i in range(0,k + 1):
    if t[cur] > 0:
        mod_max = i
        rep_start = vis.index(cur)
        flag = 1
        break
    t[cur] += 1
    vis.append(cur)
    cur = a[cur - 1]
if flag == 0:
    print(vis[-1])
    sys.exit()
mod = mod_max - rep_start
vis_mod = vis[mod_max - mod:]
# print(mod_max,mod)
# print(rep_start)
# print(vis, vis_mod)
# print(mod, len(vis_mod))
print(vis_mod[(k - (mod_max - mod))%mod])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int,input().split()))
ans = 1
c = [1]
d = [0]*(n+5)
d[1] = 1
for j in range(1,2*n):
    i = a[c[-1]-1]
    if d[i] == 1:
        g = i
        break
    # if i in set(c):
    #     g = i
    #     break
    d[i] = 1
    c.append(i)
s = c.index(g)
r = len(c)-s
if k <=s:
    print(c[k])
else:
    b = (k-s)%r
    print(c[s+b])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
ikisaki = {}
for i in range(1, n+1):
    ikisaki[i] = A[i-1]

head = [1]
visited = set([1])
next_visit = ikisaki[1]

#print(ikisaki)

while next_visit not in visited:
    visited.add(next_visit)
    head.append(next_visit)
    next_visit = ikisaki[next_visit]

roop_back_to = next_visit
for idx, num in enumerate(head):
    if num == roop_back_to:
        roop = head[idx:]

#print(roop_back_to)
#print(head)
#print(roop)


syuki = len(roop)
if k < len(head):
    print(head[k])
else:
    k -= len(head)
    print(roop[k % syuki])

Submission status: Accepted

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

hist = [-1 for i in range(N)]
route = []
loop = []

jump = 0
cur = A[0] - 1
route.append(0)
hist[0] = jump
while hist[cur] == -1:
    jump = jump + 1
    route.append(cur)
    hist[cur] = jump
    cur = A[cur] - 1

loop = route[hist[cur]:]

#print(cur, hist, route, loop)

if K < len(route):
    print(route[K] + 1)
else:
    K = K - len(route)
    #print(K)
    K = K % len(loop)
    #print(K)
    print(loop[K] + 1)

Submission status: Accepted

Solution code:
import sys

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

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


if k<=n:
    current_posi = 0
    for i in range(k):
        current_posi = a[current_posi]
    print(current_posi+1)
    sys.exit()


posi_roop = [0]
for_search = set([0])

current_posi = 0
for i in range(n):
    current_posi = a[current_posi]
    if current_posi not in for_search:
        posi_roop.append(current_posi)
        for_search.add(current_posi)
    else:
        for j in range(len(posi_roop)):
            if posi_roop[j] == current_posi:
                true_start = j
                break
        true_roop = posi_roop[true_start:]
        consume = true_start
        break
pp = (k-consume) % len(true_roop)

print(true_roop[pp]+1)

Submission status: Accepted

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

visited = [0] * n
visited[0] = 1
visit_list = [0]
visit = 0
while True:
    new_visit = a[visit]
    if visited[new_visit] == 1:
        break
    visited[new_visit] = 1
    visit_list.append(new_visit)
    visit = new_visit

period_first_index = visit_list.index(a[visit_list[-1]])
period_list = visit_list[period_first_index:]

if k < len(visit_list):
    print(visit_list[k]+1)
elif k == len(visit_list):
    print(a[visit_list[-1]]+1)
else:
    print(period_list[(k-period_first_index)%len(period_list)]+1)

Submission status: Accepted

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)
#print(start,loop)
if start == 0 and k % loop == 0:
  print(1)
  quit()
if k < i:
  print(turn.index(k))
else:
  print(turn.index(((k-start)%loop)+start))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
past_a = [1]
first = 0
for i in range(n):
    past_a.append(a_list[past_a[-1] - 1])
    
def check(past_a):
  if len(past_a) == len(set(past_a)):
    return True
  else:
    return False
  
left = 0
right = len(past_a)

while right - left > 1:
  middle = (right + left)//2
  if check(past_a[:middle]) == True:
    left = middle
  else:
    right = middle
roop_2 = left 
roop_1 = past_a.index(past_a[roop_2])
unit = roop_2 - roop_1
p_unit = past_a[roop_1:roop_2]
if k <= left:
  print(past_a[k])
else:
  k = (k - left) % unit
  print(p_unit[k])

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

# ループを見るける
target = deque()
target_s = set()
target.append(1)
target_n = A[0]
for i in range(K):
    before = len(target_s)
    target_s.add(target_n)
    if len(target_s) != before:
        target.append(target_n)
        # target_s.add(target_n)
        target_n = A[target_n-1]
    else:
        if target[-1] != 1:
            target.append(target_n)
        t = target.pop()
        t = target.index(t)
        if t != 0:
            K -= len(target)
        K = K%(len(target) - t)
        print(target[K+t])
        sys.exit()

print(target[-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
a=[0]*n
a[0]=1
nxt=A[0]-1
i=2
while 1:
  a[nxt]=i
  nxt=A[nxt]-1
  i+=1
  if a[nxt]!=0:
    g=i-a[nxt]
    t=a[nxt]-1
    break
if t>=k:
  print(a.index(k+1)+1)
else:
  k-=t
  u=k%g
  print(a.index(t+u+1)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)

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

town_line = []
town_set = set()
last_town = None


def search(town=0):
    global last_town
    if town not in town_set:
        town_line.append(town)
        town_set.add(town)
        search(town=A[town]-1)
    else:
        last_town = town
        return


search(0)
town_loop = town_line[town_line.index(last_town):]

if K < len(town_line):
    print(town_line[K] + 1)
else:
    k = K - len(town_line) + 1
    k = k % len(town_loop)
    print(town_loop[k - 1] + 1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
DestList = list(map(int,input().split()))
Count = [0 for i in range(N)]
CurrTown = 1
Count[0] = 1
Flag = 0
Loop1 = 0
Loop2 = 0
LoopNum = 0
for i in range(K):
  CurrTown = DestList[CurrTown-1]
  if(Count[CurrTown-1]==1 and Flag==0):
    Loop1 = sum(Count)
    Flag=1
  elif(Count[CurrTown-1]==2 and Flag==1):
    Loop2 = sum(Count)
    LoopNum = (K-(Loop1*2-Loop2))%(Loop2-Loop1)+(Loop1*2-Loop2)
    CurrTown = 1
    for j in range(LoopNum):
      CurrTown = DestList[CurrTown-1]
    break;
  else:
    Count[CurrTown-1]+=1
print(CurrTown)

Submission status: Accepted

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

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

fumi = set([0])
start = None
end = None
aab = [0]
for i in range(10**18):
    next = aa[aab[-1]] - 1
    if next in fumi:
        if start is None:
            start = i
            fumi = set()
        else:
            end = i
            break

    aab.append(next)
    fumi.add(next)
    if i+1 == k:
        print(next+1)
        exit(0)

random_first = len(aab) - 2*(end - start)
#print(aab, start, end, aab[start+1:end+1], aab[:random_first])

first = aab[:random_first]
one_cicle = aab[start+1:end+1]
if k <= len(first):
    print(first[k]+1)
else:
    k = k-len(first)
    print(one_cicle[k%len(one_cicle)]+1)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
visited = {}
r = []
p = 1
i = 0
while i <= n:
    if p in visited:
        s = r[0:r.index(p)]
        r = r[r.index(p):]
        break
    else:
        visited.update({p: i})
        r.append(p)
        s = r
        p = a[p - 1]
        i += 1
if k < visited[p]:
    ans = s[k]
else:
    ans = r[(k - i) % len(r)]
print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
b[1]=0
c=a[0]
d=[0]*min(k+1,10**7)
d[0]=1
for i in range(1,k+1):
    d[i]=c
    if b[c]!=-1:
        # print(i,c,b[c])
        print(d[b[c]+(k-b[c])%(i-b[c])])
        exit()
    b[c]=i    
    c=a[c-1]
print(d[-1])

Submission status: Accepted

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


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, K = IL(int)
    A = IL(lambda x: int(x) - 1)
    memo = [0]
    visited = [False] * N
    i = 0
    while(not visited[A[i]]):
        memo.append(A[i])
        visited[A[i]] = True
        i = A[i]
    if K < len(memo):
        print(memo[K] + 1)
    else:
        loop = memo[memo.index(A[i]):]
        print(loop[(K - (len(memo) - len(loop))) % len(loop)] + 1)


solve()

Submission status: Accepted

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

dic = {}

for i, a in enumerate(A, 1):
    dic[i] = a

times = {1: [0]}
count = 0
dest = 1
flg = 0
for k in range(K):
    dest = dic[dest]
    count += 1
    if dest not in times:
        times[dest] = [count]
    else:
        times[dest].append(count)
        flg = dest
        break

if count == K:
    trans = K
    dest = 1
else:
    trans = (K - count) % (times[flg][1] - times[flg][0])
    dest = flg

for t in range(trans):
    dest = dic[dest]

print(dest)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
towns = [1]
town_dic = defaultdict(lambda : 0)
prev = 1
count = 0
while True:
    next = a[prev - 1]
    count += 1
    if count == k:
        print(next)
        sys.exit()
    if town_dic[next] == 1:
        break
    else:
        town_dic[next] += 1
    towns.append(next)
    prev = next
i = towns.index(next)
repeat = towns[i:]
unit = len(repeat)
rest = k - count + 1
print(repeat[(rest % unit) - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI_()
    d = defaultdict(int)
    i = a[0]
    t = 1
    d[0] = 1
    while not d[i]:
        t += 1
        d[i] = t
        i = a[i]
    if n >= k:
        i = 0
        for _ in range(k):
            i = a[i]
        print(i + 1)
    else:
        k -= d[i] - 1
        k %= (t - (d[i] - 1))
        for _ in range(k):
            i = a[i]
        print(i + 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


def main():
    N, K = map(int, input().split())
    A = [0]
    B = [int(c) for c in input().split()]
    A.extend(B)
    dicts = {i: 0 for i in range(1, N + 1)}

    now = 1
    dicts[now] = 0
    num = 0
    flag = False
    while(num < K):
        now = A[now]
        num += 1
        if dicts[now] == 0:
            dicts[now] = num
            continue
        elif not flag:
            cycle = num - dicts[now]
            left = (K - num) % cycle
            K = left
            num = 0
            flag = True
    print(now)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
cnt = 0
pre = 1
memo = []
kumi = set([])
if k < n:
    for i in range(2 * (10 ** 5) + 5):
        cur = A[pre]
        cnt += 1
        pre = cur
        if cnt == k:
            print(cur)
            exit()

else:
    for i in range(2 * (10 ** 5) + 5):
        cur = A[pre]
        cnt += 1
        memo.append(cur)
        if cur in kumi:
            break
        kumi.add(cur)
        pre = cur
    # 今までに見た物の数を減らしておく、kは残り回数
    k -= cnt

    for j in range(cnt):
        if memo[j] == cur:
            start = j
            break
    loop = memo[start:-1]

    loop_num = i - start
    print(loop[k % loop_num])

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,K = LMIIS()
    A = LMIIS()
    visited = [False]*N
    dest = defaultdict(int)
    ep = 1
    for i,a in enumerate(A):
        dest[i+1] = a

    visited = [0]*(N+1)
    o = 1
    loop = 0
    visited[o] = loop

    while visited[dest[o]] == 0:
        loop += 1
        visited[dest[o]] = loop
        o = dest[o]
    
    # print('o=',o)
    preloop = visited[dest[o]]
    loop = loop - visited[dest[o]] + 1
    # print(preloop,loop)
    # print(visited)
    origin = 1
    if K <= preloop: 
        for i in range(K):
            origin = dest[origin]
        print(origin)
        return

    num_visit = (K - preloop) % loop
    
    for i in range(preloop):
        origin = dest[origin]
    for i in range(num_visit):
        if dest[origin] == origin:
            break
        origin = dest[origin]
    print(origin)




    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())    
a = [i - 1 for i in list(map(int, input().split()))]
# print(a)
b = []
current = 0
# cnt = 0
visited = [0 for i in range(n)]
# print("a =", a)
fr = None
while True:
    if visited[current] == 1:
        fr = current        
        break 
    visited[current] = 1
    b.append(current)
    current = a[current]
b2 = [fr]
current2 = fr
while True:
    # print("current2 =", current2)
    nextp = a[current2]
    if nextp == fr:
        break
    b2.append(nextp)
    current2 = nextp
# print("b2 =", b2)
# print("b =", b)
m = len(b)
m2 = len(b2)
if m > k:
    print(b[k] + 1)
else:
    k -= m
    k %= m2
    print(b2[k] + 1)

Submission status: Accepted

Solution code:
from itertools import count

N, K = map(int, input().split())
As = [int(n) for n in input().split()]

visited = []
visited_set = set()
now = 0
num = 0
idx = 0
for i in count():
    if now in visited_set:
        idx = visited.index(now)
        num = len(visited) - idx
        break
    visited_set.add(now)
    visited.append(now)
    now = As[now] - 1

if K <= idx:
    print(visited[K] + 1)
else:
    print(visited[idx + (K - idx) % num] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
d[1]=0
cnt=1
li=[1]
for i in range(n):
    cnt=a[cnt-1]
    li.append(cnt)
    if cnt in d.keys():
        x=i+1
        break
    else:
        d[cnt]=i+1
if k<d[cnt]:
    print(li[k])
else:
    print(li[((k-d[cnt])%(x-d[cnt]))+d[cnt]])

Submission status: Accepted

Solution code:
import numpy as np

N, K = list(map(int, input().split()))
A = np.fromstring(input(), int, sep=" ")

p = 1
count = 0
memo = {1: 0}
while count < K:
    p = A[p-1]
    count += 1

    if p not in memo:
        memo[p] = count
    else:
        step = count - memo[p]
        count += max(0, K-count) // step * step
        memo = {p: count}

print(p)

Submission status: Accepted

Solution code:
# 2020/05/10
# AtCoder Beginner Contest 167 - D

# Input
n, k = map(int,input().split())
a = list(map(int,input().split()))
a.insert(0, -1)

# Calc
idx = a[1]
sendto = [0] * (n+1)
passed = [0] * (n+1)
sendto[0] = 1

cnt = 1
roopst = -1
while(idx != 1):
    if passed[idx] == 1:
        roopst = idx
        break
    sendto[cnt] = idx
    passed[idx] = 1
    cnt = cnt + 1
    idx = a[idx]

if roopst != -1:
    for i in range(n):
        if sendto[i] == roopst:
            roopstidx = i
            break
    if k < cnt:
        tgt = k % cnt
    else:
#        tgt = ((k-roopstidx) % cnt) + roopstidx + 1
        tgt = ((k-roopstidx) % (cnt-roopstidx)) + roopstidx

else:
    tgt = k % cnt

ans = sendto[tgt]

# Output
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))

# A[0]から出発して何回でループするか数える

visited = [0]*n


def dfs(v):
    if visited[v]+1 == 3:
        return 0
    visited[v] += 1
    dfs(A[v])


dfs(0)

c = Counter(visited)
loop_cnt = c[2]
init_cnt = c[1]
k_ = k-init_cnt
k_ %= loop_cnt

cnt = 0
visited = [0]*n


ans = 0
loop = k if k < init_cnt else k_+init_cnt
for _ in range(loop):
    ans = A[ans]
print(ans+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [int(v)-1 for v in input().split()]
p = 0
memo = {}
for i in range(K):
  if p in memo:
    interval = i-memo[p]
    rest = (K-i-1)%interval
    for j in range(rest+1):
      p=A[p]
    print(p+1)
    exit()
  else:
    memo[p] = i
  p = A[p]
print(p+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
ct = 0
l = [0] * n
l[0] = 1
time =[0] * n

while l[ct] <= 1:
    time[ct] = count
    ct = a[ct] - 1
    count += 1
    l[ct] += 1
    if count == k:
        print(ct+1)
        exit()
        
roop = count - time[ct]
r = (k - count) % roop
for i in range(r):
    ct = a[ct] - 1
print(ct + 1)