Submission #5237629


Source Code Expand

import sys
sys.setrecursionlimit(10000000)


class SegmentTree():
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0]*(2*self.size - 1)
        self.node_index = [0]*(2*self.size - 1)
        for i in range(self.size):
            ind = i + (self.size - 1)
            self.node_index[ind] = i
            while ind > 0:
                ind = (ind - 1) // 2
                self.node_index[ind] = self.node_index[2*ind+1]
    
    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            if self.node[2*i+1] <= self.node[2*i+2]:
                self.node[i] = self.node[2*i+1]
                self.node_index[i] = self.node_index[2*i+1]
            else:
                self.node[i] = self.node[2*i+2]
                self.node_index[i] = self.node_index[2*i+2]

    def get_min(self, begin, end, k=0, l=0, r=-1):
        begin += (self.size - 1)
        end += (self.size - 1)
        res = float("inf")
        res_index = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                if res > self.node[end]:
                    res = self.node[end]
                    res_index = self.node_index[end]
                elif res == self.node[end]:
                    res_index = min(res_index, self.node_index[end])
            if (begin - 1) & 1:
                if res > self.node[begin]:
                    res = self.node[begin]
                    res_index = self.node_index[begin]
                elif res == self.node[begin]:
                    res_index = min(res_index, self.node_index[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return res_index, res


def dfs(node, parent_node, dep):
    id[node] = k[0]
    vs[k[0]] = node
    depth[k[0]] = dep
    k[0] += 1
    for child_node in tree[node]:
        if parent_node != child_node:
            dfs(child_node, node, dep+1)
            vs[k[0]] = node
            depth[k[0]] = dep            
            k[0] += 1
            
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    node1, node2 = map(int, input().split())
    tree[node1-1].append(node2-1)
    tree[node2-1].append(node1-1)

k = [0]
id = [0]*n
depth = [0]*(2*n-1)
vs = [0]*(2*n-1)
dfs(0,-1,0)


st = SegmentTree(2*n-1)
for i in range(2*n-1):
    st.update(i, depth[i])

q = int(input())
info = [list(map(int, input().split())) for i in range(q)]

#print(vs)
#print(depth)
#print(id)
#print(st.node)
#print(st.node_index)
for i in range(q):
    begin = min(id[info[i][0]-1], id[info[i][1]-1])
    end = max(id[info[i][0]-1], id[info[i][1]-1]) + 1
    lca = vs[st.get_min(begin, end)[0]]
    print(depth[id[info[i][0]-1]] + depth[id[info[i][1]-1]] - 2*lca + 1)

Submission Info

Submission Time
Task D - 閉路
User neterukun
Language Python (3.4.3)
Score 0
Code Size 2980 Byte
Status WA
Exec Time 2111 ms
Memory 128032 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
WA × 4
TLE × 8
AC × 3
WA × 8
TLE × 16
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 18 ms 3256 KB
subtask0_sample02.txt AC 18 ms 3320 KB
subtask0_sample03.txt AC 17 ms 3256 KB
subtask1_01.txt TLE 2111 ms 128032 KB
subtask1_02.txt TLE 2111 ms 128032 KB
subtask1_03.txt WA 18 ms 3256 KB
subtask1_04.txt WA 19 ms 3320 KB
subtask1_05.txt WA 46 ms 3456 KB
subtask1_06.txt WA 43 ms 3640 KB
subtask1_07.txt TLE 2106 ms 45048 KB
subtask1_08.txt TLE 2106 ms 44936 KB
subtask1_09.txt TLE 2105 ms 44992 KB
subtask1_10.txt TLE 2106 ms 46336 KB
subtask1_11.txt TLE 2106 ms 47476 KB
subtask1_12.txt TLE 2106 ms 46048 KB
subtask2_01.txt TLE 2110 ms 128032 KB
subtask2_02.txt TLE 2111 ms 128032 KB
subtask2_03.txt WA 815 ms 22016 KB
subtask2_04.txt WA 987 ms 21900 KB
subtask2_05.txt WA 1227 ms 26988 KB
subtask2_06.txt WA 1219 ms 27108 KB
subtask2_07.txt TLE 2106 ms 44944 KB
subtask2_08.txt TLE 2106 ms 44936 KB
subtask2_09.txt TLE 2106 ms 44996 KB
subtask2_10.txt TLE 2106 ms 46396 KB
subtask2_11.txt TLE 2106 ms 47580 KB
subtask2_12.txt TLE 2106 ms 46052 KB