Submission #1159893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159893		eliiasg	Drivers (BOI24_drivers)	Pypy 3	0 / 100	492 ms	169408 KiB

Main

from heapq import *
import sys
sys.setrecursionlimit(2**16)
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):
    if parents[a] == -1:
        return a
    parents[a] = find(parents[a])
    return parents[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)
        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: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45