Submission #1127127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127127		sosuke	Toll (BOI17_toll)	Pypy 3	100 / 100	1268 ms	202948 KiB

toll

MAX_N = 50000
MAX_K = 5
MAX_J = 17
INF = float('inf')

def combine(target, a, b, k):
    """
    Combine two matrices `a` and `b` into the `target` matrix using 
    the min-sum product rule, similar to matrix multiplication.
    """
    for x in range(k):
        for y in range(k):
            for z in range(k):
                target[x][y] = min(target[x][y], a[x][z] + b[z][y])


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

dp = [[[[INF] * k for _ in range(k)] for _ in range(MAX_J)] for _ in range((n + k - 1) // k)]


for _ in range(m):
    a, b, t = map(int, input().split())
    dp[a // k][0][a % k][b % k] = t

# Precompute dp for all powers of 2 up to 2^16 (binary lifting)
for j in range(1, MAX_J):
    for i in range((n + k - 1) // k - (1 << j)):
        combine(dp[i][j], dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1], k)

results = []
# Process queries
for _ in range(o):
    a, b = map(int, input().split())
    
    ans = [[INF] * k for _ in range(k)]
    for i in range(k):
        ans[i][i] = 0
    
    curr = a // k
    dest = b // k
    
    for i in range(MAX_J - 1, -1, -1):
        if curr + (1 << i) <= dest:
            tmp = [[INF] * k for _ in range(k)]
            combine(tmp, ans, dp[curr][i], k)
            ans = tmp
            curr += (1 << i)
    
    print(-1 if ans[a % k][b % k] == INF else ans[a % k][b % k])

Compilation message (stdout)

Compiling 'toll.py'...

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

=======

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44