— Dark mode

Aalto Competitive Programming 2025 - wk7 Homework

Company Queries II

  • Start: 2025-10-08 20:00:00
  • End: 2025-10-23 20:00:00
Submission details
Task:Company Queries II
Sender:kookinnam
Submission time:2025-10-19 01:26:14 +0300
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.04 sdetails
#60.25 sdetails
#7--details
#8--details
#90.27 sdetails
#100.26 sdetails
#11ACCEPTED0.04 sdetails
#120.25 sdetails

Code

n, q = map(int, input().split())
bosses = list(map(int, input().split()))

# Build adjacency list for the tree
tree = [[] for _ in range(n + 1)]
for i, b in enumerate(bosses, start=2):
    tree[b].append(i)

LOG = 20  # Enough for 2*10^5 nodes, since 2^20 ~ 1,000,000

up = [[0] * (n + 1) for _ in range(LOG)]
depth = [0] * (n + 1)


def dfs(v, p):
    up[0][v] = p
    for i in range(1, LOG):
        up[i][v] = up[i - 1][up[i - 1][v]]
    for nxt in tree[v]:
        if nxt != p:
            depth[nxt] = depth[v] + 1
            dfs(nxt, v)


dfs(1, 1)


def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    # Lift a up to the same depth as b
    diff = depth[a] - depth[b]
    for i in range(LOG):
        if diff & (1 << i):
            a = up[i][a]

    if a == b:
        return a

    # Lift both until their parents differ
    for i in reversed(range(LOG)):
        if up[i][a] != up[i][b]:
            a = up[i][a]
            b = up[i][b]

    return up[0][a]


for _ in range(q):
    a, b = map(int, input().split())
    print(lca(a, b))

Test details

Test 1

Verdict: ACCEPTED

input
10 10
1 2 3 4 5 6 7 8 9
6 9
8 10
10 3
...
view save

correct output
6
8
3
1
8
...
view save

user output
6
8
3
1
8
...
view save

Test 2

Verdict: ACCEPTED

input
10 10
1 1 1 1 1 1 1 1 1
1 7
3 4
4 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Test 3

Verdict: ACCEPTED

input
10 10
1 1 1 1 2 3 4 4 1
1 8
2 7
8 3
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Test 4

Verdict: ACCEPTED

input
10 10
1 1 3 1 2 2 5 3 9
7 2
7 6
3 9
...
view save

correct output
2
2
3
1
1
...
view save

user output
2
2
3
1
1
...
view save

Test 5

Verdict: ACCEPTED

input
10 10
1 2 3 2 5 3 2 2 4
6 1
1 3
1 9
...
view save

correct output
1
1
1
2
2
...
view save

user output
1
1
1
2
2
...
view save

Test 6

Verdict:

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
74862
8750
16237
72298
58111
...
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 25, in <module>
    dfs(1, 1)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  [Previous line repeated 1231 more times]
  File "input/code.py", line 17, in dfs
    for i in range(1, LOG):
RecursionError: maximum recursion depth exceeded

Test 7

Verdict:

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 8

Verdict:

input
200000 200000
1 2 1 2 3 2 1 6 3 1 10 12 13 4...
view save

correct output
1
2
2
2
1
...
view save

user output
(empty)

Test 9

Verdict:

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
2796
633
633
151
2690
...
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 25, in <module>
    dfs(1, 1)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  [Previous line repeated 3590 more times]
  File "input/code.py", line 17, in dfs
    for i in range(1, LOG):
RecursionError: maximum recursion depth exceeded

Test 10

Verdict:

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
365
73
103
365
216
...
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 25, in <module>
    dfs(1, 1)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  [Previous line repeated 1227 more times]
  File "input/code.py", line 17, in dfs
    for i in range(1, LOG):
RecursionError: maximum recursion depth exceeded

Test 11

Verdict: ACCEPTED

input
2 4
1
1 1
1 2
2 1
...
view save

correct output
1
1
1
2
view save

user output
1
1
1
2
view save

Test 12

Verdict:

input
200000 200000
1 1 2 3 4 5 6 7 8 9 10 11 12 1...
view save

correct output
27468
6353
27468
6353
6353
...
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 25, in <module>
    dfs(1, 1)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  File "input/code.py", line 22, in dfs
    dfs(nxt, v)
  [Previous line repeated 1231 more times]
  File "input/code.py", line 17, in dfs
    for i in range(1, LOG):
RecursionError: maximum recursion depth exceeded

Tasks

A Company Queries IIB Download Speed

Submissions (kookinnam)

2025-10-20 14:37:42 2025-10-20 14:36:42 2025-10-19 01:26:57 2025-10-19 01:26:14 2025-10-19 01:25:27 2025-10-19 01:23:43 2025-10-19 01:23:18