Submission #1195764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195764		hackstar	Jakarta Skyscrapers (APIO15_skyscraper)	Pypy 3	22 / 100	227 ms	121208 KiB

skyscraper

import sys
sys.setrecursionlimit(10**7)

inf=10**18

def pack_key(pos,power):
	return (pos<<32)|(power&0xffffffff)

def solve():
	data=sys.stdin.read().split()
	it=iter(data)
	n=int(next(it));m=int(next(it))
	a=[(0,0)]*m
	for i in range(m):
		b=int(next(it));p=int(next(it))
		a[i]=(b,p)
	pos=[0,0]
	for i in range(2):
		pos[i]=a[i][0]
	def check(id):
		return 0<=id<n
	in_list=[[] for _ in range(n)]
	for i in range(m):
		in_list[a[i][0]].append(i)
	dp={}
	vis=set()
	def dfs(id,power):
		if id==pos[1]:
			return 0
		x=pack_key(id,power)
		if x in dp:
			return dp[x]
		if x in vis:
			return inf
		vis.add(x)
		cur=inf
		if check(id+power):
			t=dfs(id+power,power)
			if t<inf:
				cur=min(cur,t+1)
		if check(id-power):
			t=dfs(id-power,power)
			if t<inf:
				cur=min(cur,t+1)
		for idx in in_list[id]:
			if a[idx][1]==power: continue
			t=dfs(id,a[idx][1])
			if t<inf:
				cur=min(cur,t)
		vis.remove(x)
		dp[x]=cur
		return cur
	
	r=dfs(pos[0],a[0][1])
	print(-1 if r>=inf else r)

solve()

Compilation message (stdout)

Compiling 'skyscraper.py'...

=======
  adding: __main__.pyc (deflated 43%)

=======

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43