제출 #1283232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283232		dev_pandey20	Drivers (BOI24_drivers)	Pypy 3	100 / 100	1313 ms	118036 KiB

Main

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # Each city is its own parent initially
        self.rank = [0]*n             # Rank helps keep trees flat

    def find(self, x):
        # Find the root of x with path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Flatten the tree
        return self.parent[x]

    def union(self, x, y):
        # Join two sets by rank
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return  # Already connected
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        elif self.rank[xroot] > self.rank[yroot]:
            self.parent[yroot] = xroot
        else:
            self.parent[yroot] = xroot
            self.rank[xroot] += 1


def solve():
    N, M, U = map(int, input().split())
    edges = []
    for _ in range(M):
        a, b, t = map(int, input().split())
        edges.append((t, a-1, b-1))  # 0-indexed cities
    edges.sort()  # Sort by travel time

    queries = []
    for i in range(U):
        a, b, p = map(int, input().split())
        queries.append((p, a-1, b-1, i))
    queries.sort()  # Sort by allowed driving time p

    dsu = DSU(N)
    ans = [None]*U
    idx = 0  # Edge pointer

    # Process queries in increasing order of p
    for p, a, b, qi in queries:
        # Add all edges with time <= p
        while idx < M and edges[idx][0] <= p:
            _, u, v = edges[idx]
            dsu.union(u, v)
            idx += 1
        # Check if cities a and b are connected
        ans[qi] = "TAIP" if dsu.find(a) == dsu.find(b) else "NE"

    # Print answers in original order
    print("\n".join(ans))


if __name__ == "__main__":
    solve()

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'Main.py'...

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

=======

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