-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathD.py
36 lines (30 loc) · 765 Bytes
/
D.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
## AC only with PyPy3
n, x, y = map(int, input().split())
d = [[float('inf')]*n for _ in range(n)]
tree = [[] for _ in range(n)]
i = 0
for i in range(n-1):
tree[i].append(i+1)
tree[i+1].append(i)
tree[x-1].append(y-1)
tree[y-1].append(x-1)
def dfs(i_, cost_, k_):
global d
stack = []
stack.append((i_, cost_, k_))
while stack:
i, cost, k = stack.pop()
if d[k][i] != float('inf') and d[k][i] < cost:
continue
d[k][i] = min(d[k][i], cost)
for j in tree[i]:
stack.append((j, d[k][i]+1, k))
#dfs(j, d[k][i]+1, k)
for k in range(n):
dfs(k, 0, k)
ans = [0]*n
for i in range(n):
for j in range(i, n):
ans[d[i][j]] += 1
for i in range(1, n):
print(ans[i])