글 읽기 - 시간 초과 질문

wanderkind 1년 전 0

pypy로 돌려도 자꾸 시간 초과가 뜨고 통과하는 테케가 없는데,

작업의 개괄을 크게 해치지 않는 선에서 시간을 줄일 방법이 뭐가 있을까요.

아니면 아예 새롭게 다시 짜는 게 좋을까요?

감사합니다.

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    
    m,n,K=map(int,input().split())
    s=[[*map(int,input().split())] for _ in range(K)]
    S=[[i]for i in range(K)]
    SS=[]
    
    for h in range(K):
        i,j=s[h]
        for k in [[1,0],[0,1],[-1,0],[0,-1]]:
            x,y=i+k[0],j+k[1]
            if 0<=x<m and 0<=y<n and [x,y] in s:
                S[h].append(s.index([x,y]))
    
    for i in range(K):
        e=[]
        for j in S[i]:
            e+=S[j][:]
        SS.append(set(e))
    
    for i in range(K-1,-1,-1):
        z=SS[:]
        del z[i]
        if SS[i] in z:
            del SS[i]
    
    y=SS[:]
    while 1:
        for i in range(len(SS)-1):
            if len(SS[i]&SS[i+1])>0:
                SS[i]=SS[i+1]=SS[i]|SS[i+1]
        if SS==y:
            break
        else:
            y=SS[:]
    
    for i in range(len(SS)-1,-1,-1):
        z=SS[:]
        del z[i]
        if SS[i] in z:
            del SS[i]
    
    print(len(SS))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 질문

wanderkind 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말