結果
問題 | No.2337 Equidistant |
ユーザー | Shirotsume |
提出日時 | 2023-06-02 21:30:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,038 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 145,100 KB |
最終ジャッジ日時 | 2024-06-08 22:21:23 |
合計ジャッジ時間 | 20,972 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
55,936 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 820 ms
136,872 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 1,016 ms
134,568 KB |
testcase_25 | WA | - |
testcase_26 | AC | 946 ms
134,224 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
ソースコード
import sys, time, randomfrom collections import deque, Counter, defaultdictinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353class segtree():def __init__(self,V,OP,E):self.n=len(V)self.op=OPself.e=Eself.log=(self.n-1).bit_length()self.size=1<<self.logself.d=[E for i in range(2*self.size)]for i in range(self.n):self.d[self.size+i]=V[i]for i in range(self.size-1,0,-1):self.update(i)def prod(self,l,r):assert 0<=l and l<=r and r<=self.nsml=self.esmr=self.el+=self.sizer+=self.sizewhile(l<r):if (l&1):sml=self.op(sml,self.d[l])l+=1if (r&1):smr=self.op(self.d[r-1],smr)r-=1l>>=1r>>=1return self.op(sml,smr)def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1])def EulerTour(s, graph):n = len(graph)visit = [False] * nvisit[s] = Trueq = [s]ret = []while q:now = q.pop()if now >= 0:ret.append(now)for to in graph[now][::-1]:if not visit[to]:visit[to] = Trueq.append(~now)q.append(to)else:ret.append(~now)return retdef CalcDepth(s, graph):INF = 2 ** 63 - 1from collections import dequen = len(graph)depth = [INF] * ndepth[s] = 0q = deque()q.append(s)while q:now = q.popleft()for to in graph[now]:if depth[to] == INF:depth[to] = depth[now] + 1q.append(to)return depthclass LCA():def __init__(self, graph):self.INF = 2 ** 63 - 1self.graph = graphself.N = len(self.graph)self.ET = EulerTour(0, self.graph)self.depth = CalcDepth(0, graph)self.disc = [-1] * (self.N)self.fin = [-1] * (self.N)for i, v in enumerate(self.ET):if self.disc[v] == -1:self.disc[v] = iself.fin[v] = iself.S = segtree([(self.ET[i], self.depth[self.ET[i]]) for i in range(len(self.ET))], lambda x, y: x if x[1] <= y[1] else y, (-1, self.INF))def lca(self, u, v):st = min(self.disc[u], self.disc[v])en = max(self.fin[u], self.fin[v]) + 1ver, _ = self.S.prod(st, en)return verdef dist(self, u, v):a = self.lca(u, v)return self.depth[u] + self.depth[v] - 2 * self.depth[a]n, q = mi()graph = [[] for _ in range(n)]for _ in range(n - 1):u, v = mi()u -= 1; v -= 1graph[u].append(v)graph[v].append(u)L = LCA(graph)for _ in range(q):s, t = mi()s -= 1; t -= 1print((1 - L.dist(s, t)) % 2)