Task: | Company Queries II |
Sender: | esya_rae |
Submission time: | 2024-10-23 18:47:51 +0300 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.04 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | ACCEPTED | 0.04 s | details |
#4 | WRONG ANSWER | 0.04 s | details |
#5 | WRONG ANSWER | 0.04 s | details |
#6 | RUNTIME ERROR | 0.29 s | details |
#7 | TIME LIMIT EXCEEDED | -- | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | RUNTIME ERROR | 0.24 s | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | ACCEPTED | 0.04 s | details |
#12 | RUNTIME ERROR | 0.23 s | details |
Code
import mathdef dfs(v, d):global g, visited, node_ids, depths, rnode_ids.append(v)depths.append(d)r[v] = len(node_ids)-1for w in g[v]:if not visited[w]:dfs(w, d + 1)node_ids.append(v)depths.append(d)visited[v] = Truedef build_tree_min(i):global depths, min_tree, k, mif i >= k + m:return math.inf, -1if i >= k:min_tree[i] = (depths[i - k], i - k)return min_tree[i]d1, i1 = build_tree_min(2 * i)d2, i2 = build_tree_min(2 * i + 1)if d1 < d2:min_tree[i] = (d1, i1)else:min_tree[i] = (d2, i2)return min_tree[i]def answer_min(a, b):global min_tree, kres = math.infvalue = -1a += kb += kwhile a <= b:if a % 2 == 1:z, v = min_tree[a]if res > z:value = vres = za += 1if b % 2 == 0:z, v = min_tree[b]if res > z:value = vres = zb -= 1a //= 2b //= 2return res, valuen, q = map(int, input().split())node_ids = []depths = []visited = [False] * ng = [[] for _ in range(n)]r = [-1] * nx = list(map(int, input().split()))for i in range(n - 1):g[x[i] - 1].append(i + 1)# print(g)dfs(0, 0)# print(*node_ids)# print(*depths)# print(*r)m = len(node_ids)k = 2 ** math.ceil(math.log(m, 2))min_tree = [math.inf] * (2 * k)build_tree_min(1)# print(k, min_tree)for i in range(q):a, b = map(int, input().split())a -= 1b -= 1v, w = answer_min(r[a], r[b])print(node_ids[w] + 1)
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
10 10 1 2 3 4 5 6 7 8 9 6 9 8 10 10 3 ... |
correct output |
---|
6 8 3 1 8 ... |
user output |
---|
6 8 1 1 8 ... |
Test 2
Verdict: ACCEPTED
input |
---|
10 10 1 1 1 1 1 1 1 1 1 1 7 3 4 4 1 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 ... |
Test 3
Verdict: ACCEPTED
input |
---|
10 10 1 1 1 1 2 3 4 4 1 1 8 2 7 8 3 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
1 1 1 1 1 ... |
Test 4
Verdict: WRONG ANSWER
input |
---|
10 10 1 1 3 1 2 2 5 3 9 7 2 7 6 3 9 ... |
correct output |
---|
2 2 3 1 1 ... |
user output |
---|
1 1 3 1 1 ... |
Test 5
Verdict: WRONG ANSWER
input |
---|
10 10 1 2 3 2 5 3 2 2 4 6 1 1 3 1 9 ... |
correct output |
---|
1 1 1 2 2 ... |
user output |
---|
1 1 1 1 2 ... |
Test 6
Verdict: RUNTIME ERROR
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
74862 8750 16237 72298 58111 ... |
user output |
---|
(empty) |
Error:
Traceback (most recent call last): File "input/code.py", line 68, in <module> dfs(0,...
Test 7
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 8
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 2 1 2 3 2 1 6 3 1 10 12 13 4... |
correct output |
---|
1 2 2 2 1 ... |
user output |
---|
(empty) |
Test 9
Verdict: RUNTIME ERROR
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
2796 633 633 151 2690 ... |
user output |
---|
(empty) |
Error:
Traceback (most recent call last): File "input/code.py", line 68, in <module> dfs(0,...
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
365 73 103 365 216 ... |
user output |
---|
(empty) |
Test 11
Verdict: ACCEPTED
input |
---|
2 4 1 1 1 1 2 2 1 ... |
correct output |
---|
1 1 1 2 |
user output |
---|
1 1 1 2 |
Test 12
Verdict: RUNTIME ERROR
input |
---|
200000 200000 1 1 2 3 4 5 6 7 8 9 10 11 12 1... |
correct output |
---|
27468 6353 27468 6353 6353 ... |
user output |
---|
(empty) |
Error:
Traceback (most recent call last): File "input/code.py", line 68, in <module> dfs(0,...