Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3646

Problem Lang User Status Time Memory
Lowest Common Ancestor python3 (anonymous) TLE 5000 ms 51.53 MiB

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 4.12 MiB
line_00 TLE 5000 ms -1 Mib
line_01 TLE 5000 ms -1 Mib
line_02 AC 3388 ms 51.53 MiB
line_03 TLE 5000 ms -1 Mib
line_04 TLE 5000 ms -1 Mib
random_00 TLE 5000 ms -1 Mib
random_01 TLE 5000 ms -1 Mib
random_02 AC 3179 ms 47.97 MiB
random_03 TLE 5000 ms -1 Mib
random_04 TLE 5000 ms -1 Mib

import sys input = sys.stdin.readline sys.setrecursionlimit(10000) from collections import deque, Counter, defaultdict def getN(): return int(input()) def getList(): return list(map(int, input().split())) import math MOD = 10**9 + 7 INF = 10**20 # class Segtree(): # def __init__(self, n): # self.size = 1 # while(n >= 1): # self.size = self.size << 1 # n = n//2 # # self.arr = [0 for i in range(self.size*2)] # # def update(self, k, val): # k += self.size - 1 # self.arr[k] = val # while(k): # k = (k - 1) // 2 # self.arr[k] = min(self.arr[k*2 + 1], self.arr[k*2 + 2]) # # # def query(self, a, b): # return self._query(a, b, 0, 0, self.size) # # def _query(self, a, b, k, l, r): # if r <= a and b <= l: # return INF # elif a <= r and l <= b: # return self.arr[k] # else: # return min(self._query(a, b, k*2 + 1, l, (l+r) // 2), self._query(a, b, k*2 + 2, (l+r) // 2, r)) # """ # if (r <= a | | b <= l)return INF; # else if (a <= l & & r <= b) return seg[k]; # else return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r)); # """ # # def show(self): # idx = 1 # while(idx <= self.size): # print(self.arr[idx - 1:idx * 2 - 1]) # idx *= 2 class Segtree_op(): def __init__(self, n): self.size = 1 while(n >= 1): self.size = self.size << 1 n = n//2 self.arr = [self.unit() for i in range(self.size*2)] def op(self, lch, rch): # update min with holding index if lch[0] <= rch[0]: return lch else: return rch def unit(self): return (INF, -1) def update(self, k, val): k += self.size - 1 self.arr[k] = val while(k): k = (k - 1) // 2 self.arr[k] = self.op(self.arr[k*2 + 1], self.arr[k*2 + 2]) def query(self, l, r): L = l + self.size R = r + self.size s = self.unit() while L < R: if R & 1: R -= 1 s = self.op(s, self.arr[R - 1]) if L & 1: s = self.op(s, self.arr[L - 1]) L += 1 L >>= 1 R >>= 1 return s def show(self): idx = 1 while(idx <= self.size): print(self.arr[idx - 1:idx * 2 - 1]) idx *= 2 # def eulertour(ret, graph, depth, root, visited): # ret.append((depth, root)) # depth += 1 # visited[root] = 1 # for nxt in graph[root]: # if visited[nxt] == 0: # eulertour(ret, graph, depth, nxt, visited) # depth -= 1 # ret.append((depth, root)) def eulertour(graph, root=0): n = len(graph) visited = [0] * n res = [] deq = deque([(0, root)]) deq2 = deque() while(deq): depth, current = deq.pop() res += [(depth, current)] if visited[current]: continue for nxt in graph[current]: if visited[nxt]: deq += [(depth-1, nxt)] else: deq2 += [(depth+1, nxt)] deq.extend(deq2) deq2 = deque() visited[current] = 1 return res def main(): n,q = getList() graph = [[] for i in range(n)] for i, a in enumerate(getList()): graph[i+1].append(a) graph[a].append(i+1) depth = 0 # print(graph) # eulertour(ret, graph, depth, 0, visited) ret = eulertour(graph) # print(ret) revidx = [-1 for i in range(n)] for i, point in enumerate(ret): if revidx[point[1]] == -1: revidx[point[1]] = i seg = Segtree_op(len(ret)) for i, r in enumerate(ret): seg.update(i,r) # print(revidx) # seg.show() for _ in range(q): ql, qr = getList() segl, segr = revidx[ql], revidx[qr] if segl > segr: segl, segr = segr, segl print(seg.query(segl, segr)[1]) if __name__ == "__main__": main()