Submission #1210172

#TimeUsernameProblemLanguageResultExecution timeMemory
1210172jiayiiyaijDrivers (BOI24_drivers)Pypy 3
100 / 100
1242 ms120272 KiB
# 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%)

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