Contest Duration: - (local time) (100 minutes) Back to Home

Submission #856697

Source Code Expand

Copy
n = int(raw_input())
har = map(int , raw_input().split())
L = int(raw_input())
q = int(raw_input())

from collections import deque

def bfs(g, start):
queue, enqueued = deque([(None, start)]), set([start])
while queue:
parent, n = queue.popleft()
yield parent, n
new = set(g[n]) - enqueued
enqueued |= new
queue.extend([(n, child) for child in new])

def s_p(g, start, end):
parents = {}
for parent, child in bfs(g, start):
parents[child] = parent
if child == end:
revpath = [end]
while True:
parent = parents[child]
revpath.append(parent)
if parent == start:
break
child = parent
return list(reversed(revpath))
return None # or raise appropriate exception

graph = {i:[] for i in xrange(n)}
for i in xrange(n):
if i - 1 >= 0:graph[i].append(i-1)
if i + 1 <= n-1:graph[i].append(i+1)
for i in xrange(q):
a,b = map(int , raw_input().split())
a-=1
b-=1
path = s_p(graph,a,b)
ans = 0
sm = 0
#print path
pre = har[path[0]]
psm = 0
cost = []
pp = 0
for ix in xrange(1,len(path)):
sm += abs(har[path[ix]] - pre)
psm += abs(har[path[ix]] - pre)
pre = har[path[ix]]
if sm > L:
ans += 1
sm -= pp
if sm == L:
sm = 0
ans += 1
cost.append(sm)
pp = sm
if sm > 0:
ans += 1
print ans

#### Submission Info

Submission Time 2016-08-28 22:16:48+0900 C - Tak and Cards har_vi PyPy2 (5.6.0) 0 1609 Byte RE 73 ms 9072 KB

#### Judge Result

Score / Max Score 0 / 0 0 / 200 0 / 100
Status
 RE × 4
 RE × 12
 RE × 24
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Case Name Status Exec Time Memory
example_01.txt RE 73 ms 9072 KB
example_02.txt RE 59 ms 8944 KB
example_03.txt RE 59 ms 8944 KB
example_04.txt RE 58 ms 8944 KB
subtask1_01.txt RE 59 ms 8944 KB
subtask1_02.txt RE 62 ms 8944 KB
subtask1_03.txt RE 63 ms 8944 KB
subtask1_04.txt RE 63 ms 8944 KB
subtask1_05.txt RE 63 ms 8944 KB
subtask1_06.txt RE 62 ms 8944 KB
subtask1_07.txt RE 60 ms 8944 KB
subtask1_08.txt RE 63 ms 8944 KB
subtask1_09.txt RE 63 ms 8944 KB
subtask2_01.txt RE 63 ms 8944 KB
subtask2_02.txt RE 63 ms 8944 KB
subtask2_03.txt RE 63 ms 8944 KB
subtask2_04.txt RE 63 ms 8944 KB
subtask2_05.txt RE 65 ms 8944 KB
subtask2_06.txt RE 61 ms 8944 KB
subtask2_07.txt RE 60 ms 8944 KB
subtask2_08.txt RE 63 ms 8944 KB
subtask2_09.txt RE 64 ms 8944 KB
subtask2_10.txt RE 65 ms 8944 KB
subtask2_11.txt RE 64 ms 8944 KB