Submission #1210171

#TimeUsernameProblemLanguageResultExecution timeMemory
1210171bisonbisonDrivers (BOI24_drivers)Pypy 3
11 / 100
2088 ms269992 KiB
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 = [i for i in range(n)]

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 49%)

=======
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...