Submission #1210162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210162		bisonbison	Drivers (BOI24_drivers)	Pypy 3	55 / 100	2101 ms	146280 KiB

Main

from heapq import heappush, heappop

elements = [0,1,2,3,4,5]

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()]
    roads.append((t, a-1,b-1))

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


queeries = sorted(queeries)
roads = sorted(roads)

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):
        answere.append((q, "TAIP"))
    else:
        answere.append((q,"NE"))

answere = sorted(answere)
for a in answere:
    print(a[1])

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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