Submission #1098265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098265		vjudge1	Evacuation plan (IZhO18_plan)	Pypy 2	0 / 100	20 ms	19260 KiB

plan

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 i in range(m):
    u, v, d = map(int, input().split())
    bridges.append((d, u-1, v-1, i))

q = int(input())
queries = []
for i 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], b-1)
    else:
        s, w = params
        queries.append((w, s-1, i))

bridges.sort(reverse=True, key=lambda x: x[0])
queries.sort(reverse=True, key=lambda x: x[0])

answers = [-1] * len(queries)
uf = UnionFind(n)
bridge_index = 0

for w, s, query_index in queries:
    while bridge_index < len(bridges) and bridges[bridge_index][0] >= w:
        _, u, v, _ = bridges[bridge_index]
        uf.union(u, v)
        bridge_index += 1
    root_s = uf.find(s)
    reachable = sum(1 for i in range(n) if uf.find(i) == root_s)
    answers[query_index] = reachable

for answer in answers:
    print(answer)

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46