— 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:banghalq
Submission time:2025-10-10 15:12:54 +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.36 sdetails
#7ACCEPTED0.76 sdetails
#8--details
#90.37 sdetails
#100.39 sdetails
#11ACCEPTED0.04 sdetails
#120.36 sdetails

Code

max_log = 18
n, q = [int(x) for x in input().split()]

ancestors = [[0 for _ in range(max_log)] for _ in range(n+1)] #ancestor[i][j] = 2**jth ancestor of i
depths = [0 for _ in range(n+1)]

GRAPH = {i:[] for i in range(n+1)}
for i, x in enumerate(input().split()):
    x = int(x)
    GRAPH[i+2].append(x)
    GRAPH[x].append(i+2)

def dfs(node, parent):
    ancestors[node][0] = parent
    for i in range(max_log):
        if ancestors[node][i-1] != 0:
            ancestors[node][i] = ancestors[ancestors[node][i-1]][i-1]
    for adj in GRAPH[node]:
        if adj != parent:
            depths[adj] = depths[node] + 1
            dfs(adj, node)

dfs(1, 0)

def res(a, b):
    if depths[a] < depths[b]:
        a, b = b, a
    
    diff = depths[a] - depths[b]
    for i in range(max_log):
        if (diff >> i) & 1:
            a = ancestors[a][i]

    if a == b:
        return a

    for i in range(max_log-1, -1, -1):
        if ancestors[a][i] != ancestors[b][i]:
            a = ancestors[a][i]
            b = ancestors[b][i]
    return ancestors[a][0]

sol = []
for _ in range(q):
    a, b = [int(x) for x in input().split()]
    sol.append(res(a, b))

for elt in sol:
    print(elt)

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 23, in <module>
    dfs(1, 0)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  [Previous line repeated 1231 more times]
  File "input/code.py", line 15, in dfs
    for i in range(max_log):
RecursionError: maximum recursion depth exceeded

Test 7

Verdict: ACCEPTED

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
1
1
1
1
1
...
view save

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 23, in <module>
    dfs(1, 0)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  [Previous line repeated 3292 more times]
  File "input/code.py", line 15, in dfs
    for i in range(max_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 23, in <module>
    dfs(1, 0)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  [Previous line repeated 1848 more times]
  File "input/code.py", line 18, in dfs
    for adj in GRAPH[node]:
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 23, in <module>
    dfs(1, 0)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  File "input/code.py", line 21, in dfs
    dfs(adj, node)
  [Previous line repeated 1231 more times]
  File "input/code.py", line 15, in dfs
    for i in range(max_log):
RecursionError: maximum recursion depth exceeded

Tasks

A Company Queries IIB Download Speed

Submissions (banghalq)

2025-10-14 13:16:39 2025-10-14 13:14:59 2025-10-10 15:12:54 2025-10-10 14:46:25