Submission #1210172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210172		jiayiiyaij	Drivers (BOI24_drivers)	Pypy 3	100 / 100	1242 ms	120272 KiB

Main

# https://oj.uz/problem/view/BOI24_drivers  30/05 - 2025

class UF:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.size = [1]*n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        
        grandparent = self.find(self.parent[x])
        self.parent[x] = grandparent
        return grandparent
    
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if a == b:
            return
        
        if self.size[a] < self.size[b]:
            a, b = b, a
        
        self.parent[b] = a
        self.size[a] += self.size[b]
    
    def check(self, a, b):
        return self.find(a) == self.find(b)

import sys

n, m, u = map(int, sys.stdin.readline().split())

roads = []
for i in range(m):
    x, y, t = map(int, sys.stdin.readline().split())
    roads.append((t, x-1, y-1))
roads.sort()
roads.append([1e10])

queries = []
for i in range(u):
    a, b, p = map(int, sys.stdin.readline().split())
    queries.append((p, a-1, b-1, i))
queries.sort()

uf = UF(n)
ans = [[] for _ in range(u)]
index = 0
for q in range(u):
    p, a, b, i = queries[q]
    while roads[index][0] <= p:
        uf.union(roads[index][1], roads[index][2])
        index += 1
    if uf.check(a, b):
        ans[i] = "TAIP"
    else:
        ans[i] = "NE"

for i in range(u):
    print(ans[i])

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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