글 읽기 - [python, pypy3] 시간초과 질문드립니다.

dkssudckdah 4년 전 0

질의 2가 나오기 전까지 질의 1을 저장해 두었다가 한번에 처리하는 방식으로 하였는데 45%에서 시간초과가 계속 발생하여 질문드립니다.

import sys
input = sys.stdin.readline


def bfs():
    visited = [0] * (N + 1)
    visited[C] = 1
    q = [C]
    depth = 1
    table = [[None, depth] for _ in range(N + 1)]
    while q:
        depth += 1
        qs, q = q, []
        for vertex in qs:
            for target in adj[vertex]:
                if not visited[target]:
                    visited[target] = 1
                    q.append(target)
                    table[target][0] = vertex
                    table[target][1] = depth
    return table


N, C = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    f, t = map(int, input().split())
    adj[f].append(t)
    adj[t].append(f)

table = bfs()

tank = [0] * (N + 1)
result = []
cases = [list(map(int, input().split())) for _ in range(int(input()))]
dic = {}
for method, v in cases:
    if method == 1:
        if v not in dic:
            dic[v] = 1
        else:
            dic[v] += 1
    else:
        for key in dic:
            target = key
            while True:
                if table[target][0] == None:
                    tank[target] += dic[key]
                    break
                else:
                    tank[target] += dic[key]
                    target = table[target][0]
        result.append(str(tank[v] * table[v][1]))
        dic = {}

print("\n".join(result))

lovinix 4년 전 1

쿼리1 쿼리2 1,2... 형태로 반복된다면 시간이 얼마나 걸릴까요?

dkssudckdah 4년 전 0

@lovinix 답변 감사드립니다.

그 경우에 어떻게 해야할지 모르겠습니다. 쿼리 2 종류가 무작위로 들어오는데 한번에 처리하는 방법이 있을까요?

lovinix 4년 전 1

질문자님이 푸신 문제 목록을 보았는데, 이 문제는 아직 풀기에 조금 이른 것 같습니다.

정해는 아마 세그먼트트리를 이용한 풀이일것같으니 공부해서 풀고싶으시다면 오일러 투어 테크닉과 세그먼트트리를 찾아보세요

dkssudckdah 4년 전 0

@lovinix 댓글 남겨주셔서 감사합니다.

세그먼트트리를 공부하고 다시 시도해보겠습니다.

dtc03012 4년 전 2

트리를 일자로 편 다음에 1번 쿼리가 들어올 때 그 값 증가시켜주고 2번 쿼리 들어올 때 구간합 구해주세요

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

문제

문제

출처

ICPC

[python, pypy3] 시간초과 질문드립니다.

dkssudckdah 4년 전 0

lovinix 4년 전 1

dkssudckdah 4년 전 0

lovinix 4년 전 1

dkssudckdah 4년 전 0

dtc03012 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말