Submission #1210169

#TimeUsernameProblemLanguageResultExecution timeMemory
1210169julleeDrivers (BOI24_drivers)Pypy 3
100 / 100
1327 ms121556 KiB
n, m, u = map(int, input().split())


parent = [i for i in range(n)]
sz = [1 for _ in range(n)]



def find(i):

    if i != parent[i]:
        parent[i] = find(parent[i])

    return parent[i]

def unify(p, q):

    root1, root2 = find(p), find(q)

    if root1 == root2:
        return
    
    if sz[root1] < sz[root2]:
        root1, root2 = root2, root1

    sz[root1] += sz[root2]
    parent[root2] = root1




roads = []
cur_road_idx = 0
for i in range(m):
    x, y, t = map(int, input().split())
    x -= 1
    y -= 1
    roads.append((t, x, y))

roads.sort()

queries = []
answers = [-1 for _ in range(u)]

for i in range(u):
    a, b, t = map(int, input().split())
    queries.append((t, a, b, i))

queries.sort()


time_constraint = 0


for query in queries:

    t, a, b, q_idx = query

    a -= 1
    b -= 1

    if t > time_constraint:

        while cur_road_idx < m:

            tt, x, y = roads[cur_road_idx]
            
            if tt > t:
                break

            unify(x, y)
            cur_road_idx += 1

    answers[q_idx] = find(a) == find(b)
    

for answer in answers:

    if answer:
        print("TAIP")
    else:
        print("NE")
            

Compilation message (stdout)

Compiling 'Main.py'...

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

=======
#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...