How to reduce the runtime of a python script?

Question

I have been for a few days trying to solve a programming problem that involves searching to find the union and the intersection between sets.

I managed to solve the problem with small sets, but when the set starts to get very large, no matter how much program arrives in the answer, I get a "Time limit exceeded".

I made a similar program in c++ and the code was accepted, but in python it simply did not pass...

I optimized my program as much as possible, but the runtime hasn’t changed enough...

My question is:

• There are ways to further reduce runtime with python programs?

The problem boils down to a given number of sets. For example

Set 1: -> 1 1

Set 2: -> 2 1 5

Set 3: -> 3 2 4 6

Set 4: -> 4 1 3 5 7

And given certain operations between sets returns:

(1: Number of elements other than the intersection)

(2: Quantity of items other than union)

Example of operations:

Case 1: -> 1 1 2 (Intersection between set 1 and set 2)

Case 2: -> 2 1 4 (Union between set 1 and set 4)

Case 3: -> 1 3 4 (Intersection between set 3 and set 4)

Case 4: -> 2 2 4 (Union between set 2 and set 4)

Program I made:

def main():
    # Casos de Teste
    for i in range(int(input())):

        lis = []
        # Quantidade de Conjuntos
        for j in range(int(input())):
            # Lista com todos os números do conjunto
            lis.append(list(map(int, input().split())))

            # O primeiro elemento é a quantidade de números do 
            conjunto
            lis[j].pop(0)

        # Quantidade de operçãoes
        for j in range(int(input())):
            # Operação e conjuntos escolhidos
            op, l1, l2 = map(int, input().split())

            # Interseção
            if(op == 1):
                # -1 por conta do index da lista
                inte = set(lis[l1-1]) & set(lis[l2-1])
                print(len(inte))

            # União
            else:
                union = set(lis[l1-1]) | set(lis[l2-1])
                print(len(union))

if __name__ == "__main__":
    main()

The link to the question is: https://www.urionlinejudge.com.br/judge/pt/problems/view/2222

Answer 1

I sent your code as python 3 and it was accepted without any modification... See below screenshot of the result:

I made a version that got a little faster than yours; To save time I did not convert the numbers to integer, and I have already managed sets directly (no intermediate lists):

T = int(input()) # Quantidade de instancias
for num_instancia in range(T):
    N = int(input()) # Quantidade de conjuntos
    conjuntos = {str(num_conjunto+1): set(input().split()[1:])
        for num_conjunto in range(N)} # le os conjuntos
    Q = int(input()) # quantas operacoes
    for n_op in range(Q):
        tipo, conj1, conj2 = input().split() # le a operacao
        if tipo == '1': # intersecao
            print(len(conjuntos[conj1] & conjuntos[conj2]))
        elif tipo == '2': # uniao
            print(len(conjuntos[conj1] | conjuntos[conj2]))

Upshot: