Submission #1159901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159901		eliiasg	Drivers (BOI24_drivers)	Pypy 3	100 / 100	1261 ms	130580 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

def find(a):
    vis = [a]
    while parents[a] != -1:
        a = parents[a]
        vis.append(a)
    for e in vis[:-1]:
        parents[e] = a
    return a

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

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

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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