Submission #1210242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210242		bisonbison	Drivers (BOI24_drivers)	Pypy 3	11 / 100	2071 ms	270892 KiB

Main

from heapq import heappush, heappop

def find_root(a):
    if elements[a] == a:
        return a
    
    elements[a] = find_root(elements[a])
    return elements[a]

def unite(a,b):
    a = find_root(a)
    b = find_root(b)
    if a==b:return 0

    elements[a] = b

n,m,u = [int(x) for x in input().split()]
elements = []
for  i in range(n):
    elements.append(i)

roads = []
for i in range(m):
    a,b,t = [int(x) for x in input().split()]
    heappush(roads, (t, a-1, b-1))

queeries = []
for querry in range(u):
    a,b,p = [int(x) for x in input().split()]
    heappush(queeries, (p,a-1,b-1,querry))

t = 0
c = 0
d = 0

answere = []

for i in range(u):
    p, a, b, q = heappop(queeries)

    while t <= p:
        if t <= p:
            unite(c,d)
        try:
            t, c, d = heappop(roads)
        except:
            break
        
    if find_root(a) == find_root(b):
        heappush(answere,(q,"TAIP"))
    else:
        heappush(answere,(q,"NE"))

svar = ""
for i in range(len(answere)):
    q, string = heappop(answere)
    svar += string+"\n"

print(svar)

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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