Местоположение
Россия, Москва и Московская обл., Москва

Достижения

Все достижения (1)

Наибольший вклад в теги

Все теги (11)

Лучшие ответы пользователя

Все ответы (7)
  • Как максимально ускорить данный код на Python?

    @keddad Автор вопроса
    Ученик
    Окей, в итоговой версии я избавился от рекурсии, типизации и Arrayев. Основной профит получил от рекурсии, конечно. Этого не хватило для решения задачи, но код заметно ускорился.
    n, m = map(int, input().split())
    
    parent, weight, rank = [-1 for _ in range(n)], [0 for _ in range(n)], [1 for _ in range(n)]
    
    
    def find_set(v):
        while parent[v] != -1 and parent[v] != v:
            parent[v] = parent[parent[v]]
            weight[parent[v]] += weight[v]
            weight[v] = 0
            v = parent[v]
        if parent[v] == -1:
            parent[v] = v
        return v
    
    
    def union_sets(a, b, cost):
        a = find_set(a)
        b = find_set(b)
        if a != b:
            if rank[a] < rank[b]:
                a, b = b, a
            parent[b] = a
            weight[a] += cost
            weight[a] += weight[b]
            weight[b] = 0
            if rank[a] == rank[b]:
                rank[a] += 1
        else:
            weight[a] += cost
    
    
    def main():
        with open("input.txt", "r") as inp:
            with open("output.txt", "w") as out:
                inp.__next__()
                for line in inp:
                    st = line.split()
                    if len(st) != 4:
                        out.write(str(weight[find_set(int(st[1]) - 1)]) + "\n")
                    else:
                        union_sets(int(st[1]) - 1, int(st[2]) - 1, int(st[3]))
    
    
    main()
    Ответ написан
    1 комментарий

Лучшие вопросы пользователя

Все вопросы (33)