Memory Limit Exceeded on interactive problem what can be the reason?

Revision en1, by khan_ali, 2024-10-26 13:20:27

Here is my code for [problem:https://codeforces.net/contest/1991/problem/E]. I am getting memory limit exceeded on test case 2. Strange. I am doing bfs first then simply intracting with the judger.

import sys
input = sys.stdin.readline

def solve(n , m, graph):
    # print(graph)
    ans = [set(), set()]
    visited = [False] * (n + 1)
    stack = [(1, 0, -1)]
    alice_win = False
    while stack and not alice_win:
        new_stack = []
        for num in stack:
            visited[num[0]] = True
            ans[num[1]].add(num[0])
            for child in graph[num[0]]:
                if child != num[2]:
                    if visited[child]:
                        if child in ans[num[1]]:
                            alice_win = True
                            break
                    else:
                        new_stack.append((child, (num[1] + 1) % 2, num[0]))
                if alice_win:
                    break
            
        stack = new_stack


    if alice_win:
        print("Alice", flush=True)
        sys.stdout.flush()
        for i in range(n):
            print(1, 2, flush=True)
            sys.stdout.flush()
            if input().strip() == "-1":
                quit()
    else:
        print("Bob", flush=True)
        sys.stdout.flush()
        # print(ans)
        ans[0] = list(ans[0])
        ans[1] = list(ans[1])
        if len(ans[0]) + len(ans[1]) != n:
            raise Exception()
        for i in range(n):
            colors = input().strip()
            if colors == "-1":
                quit()
            colors = list(map(int, colors.split()))
            if len(ans[0]) == 0:
                temp = ans[1].pop()
                if 2 in colors:
                    print(temp, 2, flush=True)
                elif 3 in colors:
                    print(temp, 3, flush=True)
                sys.stdout.flush()
                continue
            if len(ans[1]) == 0:
                temp = ans[0].pop()
                if 1 in colors:
                    print(temp, 1, flush=True)
                elif 3 in colors:
                    print(temp, 3, flush=True)
                sys.stdout.flush()
                continue
            if 1 in colors:
                temp = ans[0].pop()
                print(temp, 1, flush=True)
                sys.stdout.flush()
                continue
            if 2 in colors:
                temp = ans[1].pop()
                print(temp, 2, flush=True)
                sys.stdout.flush()
                continue
        
        



def main():
    for t in range(int(input())):
        temp = input()
        if temp == "-1":
            quit()
        n, m = map(int, temp.split())
        graph = [[] for i in range(n + 1)]
        for i in range(m):
            a,b = map(int, input().split())
            graph[a].append(b)
            graph[b].append(a)
        solve(n, m, graph)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English khan_ali 2024-10-26 13:21:06 43
en1 English khan_ali 2024-10-26 13:20:27 3089 Initial revision (published)