Submission #1098262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098262		vjudge1	Bridges (APIO19_bridges)	Pypy 2	0 / 100	25 ms	19344 KiB

bridges

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

n, m = map(int, input().split())
bridges = []
for _ in range(m):
    u, v, d = map(int, input().split())
    bridges.append((d, u-1, v-1))

q = int(input())
queries = []
for _ in range(q):
    t, *params = map(int, input().split())
    if t == 1:
        b, r = params
        bridges[b-1] = (r, bridges[b-1][1], bridges[b-1][2])
    else:
        s, w = params
        queries.append((s-1, w))

bridges.sort(reverse=True)
for s, w in queries:
    uf = UnionFind(n)
    for d, u, v in bridges:
        if d <= w:
            uf.union(u, v)
    reachable = len(set(uf.find(i) for i in range(n) if uf.find(s) == uf.find(i)))
    print(reachable)

Compilation message (stderr)

File "bridges.py", line 32
    t, *params = map(int, input().split())
       ^
SyntaxError: invalid syntax

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27