Submission #1210169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210169		jullee	Drivers (BOI24_drivers)	Pypy 3	100 / 100	1327 ms	121556 KiB

Main

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

=======

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