Submission #931615

#	Time	Username	Problem	Language	Result	Execution time	Memory
931615		dnialh	Jakarta Skyscrapers (APIO15_skyscraper)	Pypy 3	57 / 100	1067 ms	154632 KiB

skyscraper

import sys
input = sys.stdin.readline

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

adj = [[] for _ in range(n)]
sta = []

power = []
for _ in range(m):
    bi, pi = map(int, input().split())
    adj[bi].append(_)
    sta.append(bi)
    power.append(pi)

seen = [0] * n

pair = set()
amt = 0
st = [(sta[0], 0)]
while not seen[sta[1]]:
    nex = []

    def add(u, v):
        if 0 <= u < n:
            if (u, v) not in pair:
                pair.add((u, v))
                nex.append((u, v))
    
    while st:
        loc, p = st.pop()
        if not seen[loc]:
            seen[loc] = 1
            for u in adj[loc]:
                st.append((loc, power[u]))

        add(loc + p, p)
        add(loc - p, p)

    amt += 1
    st = nex

    if st == [] and not seen[sta[1]]:
        print(-1)
        sys.exit()
    
print(amt - 1)
    

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