Submission #7490027


Source Code Expand

def resolve():
    import math

    class DoublingLCA:
        """
        LCA ダブリング版
        初期化 O(NlogN)、クエリ O(logN)
        """

        def __init__(self,edges,root=0):
            """
            :param list of (list of int) edges:
            :param int root=0:
            """
            self.edges = edges
            self.n = len(edges)
            self.root = root

            self.MAX_LOG_V = self.n.bit_length()
            self.depths = [-1] * self.n
            self.parents = [[-1] * self.n for _ in range(self.MAX_LOG_V)]

            self.__dfs(-1,root,0)
            self.__doubling()

        def __dfs(self,par,cur,dep):
            self.depths[cur]=dep
            self.parents[0][cur]=par
            for v in self.edges[cur]:
                if v!=par:
                    self.__dfs(cur,v,dep+1)

        def __doubling(self):
            for k in range(self.MAX_LOG_V - 1):
                for v in range(self.n):
                    if self.parents[k][v] < 0: # 親がない
                        continue
                    self.parents[k+1][v]=self.parents[k][self.parents[k][v]]

        def get(self, u, v):
            # 深さを合わせる
            if self.depths[u] > self.depths[v]:
                u, v = v, u
            for k in range(self.MAX_LOG_V):
                if (self.depths[v] - self.depths[u]) >> k & 1:
                    v = self.parents[k][v]
            if v == u:
                return v

            # にぶたん
            for k in reversed(range(self.MAX_LOG_V)):
                if self.parents[k][u] != self.parents[k][v]:
                    u = self.parents[k][u]
                    v = self.parents[k][v]
            return self.parents[0][u]

        def distance(self, u, v):
            """
            u, v 間の距離
            depth[u] + depth[v] - depth[lca]*2
            :param u:
            :param v:
            :rtype: int
            """
            lca = self.get(u, v)
            return self.depths[u] + self.depths[v] - self.depths[lca] * 2


    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N - 1)]
    Q = int(input())
    AB = [list(map(int, input().split())) for _ in range(Q)]

    edges = [[] for _ in range(N + 1)]
    for x, y in XY:
        edges[x - 1].append(y - 1)
        edges[y - 1].append(x - 1)
    LCA = DoublingLCA(edges=edges)

    for a, b in AB:
        d = LCA.distance(a - 1, b - 1)
        print(d + 1)

resolve()

Submission Info

Submission Time
Task D - 閉路
User moni0627
Language PyPy3 (2.4.0)
Score 0
Code Size 2574 Byte
Status RE
Exec Time 1825 ms
Memory 127320 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 10
RE × 2
AC × 23
RE × 4
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 192 ms 38384 KB
subtask0_sample02.txt AC 195 ms 38256 KB
subtask0_sample03.txt AC 200 ms 38256 KB
subtask1_01.txt RE 863 ms 92248 KB
subtask1_02.txt RE 792 ms 89188 KB
subtask1_03.txt AC 193 ms 38256 KB
subtask1_04.txt AC 194 ms 38256 KB
subtask1_05.txt AC 254 ms 41712 KB
subtask1_06.txt AC 245 ms 40688 KB
subtask1_07.txt AC 847 ms 90712 KB
subtask1_08.txt AC 896 ms 96600 KB
subtask1_09.txt AC 930 ms 102360 KB
subtask1_10.txt AC 967 ms 98392 KB
subtask1_11.txt AC 984 ms 106888 KB
subtask1_12.txt AC 937 ms 104920 KB
subtask2_01.txt RE 1220 ms 110680 KB
subtask2_02.txt RE 1195 ms 110680 KB
subtask2_03.txt AC 842 ms 78296 KB
subtask2_04.txt AC 854 ms 78936 KB
subtask2_05.txt AC 937 ms 83928 KB
subtask2_06.txt AC 921 ms 83124 KB
subtask2_07.txt AC 1697 ms 127320 KB
subtask2_08.txt AC 1776 ms 125784 KB
subtask2_09.txt AC 1751 ms 121816 KB
subtask2_10.txt AC 1805 ms 122456 KB
subtask2_11.txt AC 1778 ms 120788 KB
subtask2_12.txt AC 1825 ms 121304 KB