Submission #1159880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159880		eliiasg	Drivers (BOI24_drivers)	Pypy 3	0 / 100	2112 ms	763528 KiB

Main

from heapq import *
N, M, U = map(int, input().split())
roads = sorted(tuple(reversed(list(map(int, input().split())))) for _ in range(M))[::-1]
Q = sorted(tuple(reversed(list(map(int, input().split())))) + (i,) for i in range(U))

parents = [-1]*(N+1)
out = [None]*U


for t, aq, bq, i in Q:
    while len(roads) > 0 and t >= roads[-1][0]:
        _, a, b = roads.pop()
        V = [a]
        while parents[a] != -1:
            a = parents[a]
            V.append(a)
        while parents[b] != -1:
            b = parents[b]
        for e in V:
            parents[e] = b
    
    while parents[aq] != -1:
        aq = parents[aq]
    while parents[bq] != -1:
        bq = parents[bq]
    
    out[i] = "TAIP" if aq == bq else "NE"

print("\n".join(out))

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45