Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
from queue import PriorityQueue
adj = [[] for i in range(n)]
for i in range(1, n):
    adj[i].append(i-1) 
    adj[i-1].append(i)
adj[x-1].append(y-1)
adj[y-1].append(x-1)
d = [[10**4]*n for i in range(n)]
def bfs(s):
    q = PriorityQueue()
    d[s][s] = 0
    q.put((0,s))
    while not q.empty():
        cd, c = q.get()
        for a in adj[c]:
            if d[s][a] > d[s][c] + 1:
                d[s][a] = d[s][c] + 1
                q.put((d[s][a], a))
for i in range(n):
    bfs(i)
ks = [0]*n
for i in range(n):
    for j in range(n):
        if d[i][j] < n:
            ks[d[i][j]] += 1
for i in range(1, n):
    print (ks[i]//2)
for i in range(10**7):
    a = 1 + 1

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
from queue import Queue
adj = [[] for i in range(n)]
for i in range(1, n):
    adj[i].append(i-1) 
    adj[i-1].append(i)
adj[x-1].append(y-1)
adj[y-1].append(x-1)
d = [[10**4]*n for i in range(n)]
def bfs(s):
    q = Queue()
    d[s][s] = 0
    q.put(s)
    while not q.empty():
        c = q.get()
        for a in adj[c]:
            if d[s][a] > d[s][c] + 1:
                d[s][a] = d[s][c] + 1
                q.put(a)
for i in range(n):
    bfs(i)
ks = [0]*n
for i in range(n):
    for j in range(n):
        if d[i][j] < n:
            ks[d[i][j]] += 1
for i in range(1, n):
    print (ks[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,x,y = readInts()

d = defaultdict(int)

for i in range(1,n+1):
	for j in range(1,n+1):
		d[min(abs(i-j),abs(i-x)+1+abs(y-j),abs(i-y)+1+abs(j-x))]+=1

for i in range(1,n):
	print(d[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

n, x, y = map(int, input().split())
ans = [0] * (n - 1)

x -= 1
y -= 1
for i in range(n):
    for j in range(n):
        c = min(abs(i - j), abs(i-x)+abs(j-y)+1,abs(i-y)+abs(j-x)+1)
        if c:
            ans[c-1] += 1

for ai in ans:
    print(ai//2)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

n,x,y = map(int,input().split())
G = nx.Graph()
G.add_nodes_from(list(range(n)))
inf = 10**10
for i in range(n-1):
    G.add_edge(i,i+1)
G.add_edge(x-1,y-1)

s = set()
ans = [0]*(n-1)
paths = nx.shortest_path(G)
for i in range(n):
    for j in range(n):
        if (min(i,j),max(i,j)) in s:
            pass
        else:
            s.add((min(i,j),max(i,j)))
            c = len(paths[i][j])-1
            if c:
                ans[c-1] += 1
for ai in ans:
    print(ai)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

n,x,y = map(int,input().split())
G = nx.Graph()
G.add_nodes_from(list(range(n)))
inf = 10**10
D = [[inf]*n for i in range(n)]
for i in range(n-1):
    #G[i].append(i+1)
    #G[i+1].append(i)
    G.add_edge(i,i+1)
    D[i][i+1] = 1
    D[i+1][i] = 1
G.add_edge(x-1,y-1)
D[x-1][y-1] = 1
D[y-1][x-1] = 1

for i in range(n):
    D[i][i] = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            D[i][j] = min(D[i][j],D[i][k]+D[k][j])

s = set()
ans = [0]*(n-1)
paths = nx.shortest_path(G)
for i in range(n):
    for j in range(n):
        if (min(i,j),max(i,j)) in s:
            pass
        else:
            s.add((min(i,j),max(i,j)))
            c = len(paths[i][j])-1
            if c:
                ans[c-1] += 1
for ai in ans:
    print(ai)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N, X, Y = map(int, input().split())

for k in range(1, N):
    count = 0
    for i, j in combinations(range(1, N+1), 2):
        if min(j - i, abs(X-i)+1+abs(Y-j)) == k:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, X, Y = map(int, input().split())

graph = [[] for _ in range(N+1)]
ans = []

for i in range(N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)


#print(graph)

for j in range(N):
    dist = [-1] * (N+1)
    #dist[j] = 0
    dist[j+1] = 0

    d = deque()
    d.append(j+1)
    #BFS実行部分
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
    ans.extend(dist[j+2:])

#print(ans)
for i in range(1, N):
    print(ans.count(i))
#print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
N,X,Y=map(int,input().split())
graph=[[] for _ in range(N)]

for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
    
graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

answer=[0 for i in range(N)]
for i in range(N):
    d=deque([i])
    dist=[-1 for _ in range(N)]
    dist[i]=0
    while d:
        v=d.popleft()
        for i in graph[v]:
            if dist[i]!=-1:
                continue
            dist[i]=dist[v]+1
            d.append(i)
    for j in range(1,N):
        answer[j]+=dist.count(j)
for j in range(1,N):
    print(int(answer[j]/2))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())

cost = [[float("inf")]*n for i in range(n)]

for i in range(n-1):
    cost[i][i+1]=1
    cost[i+1][i]=1
cost[x-1][y-1]=1
cost[y-1][x-1]=1

def dijkstra(s):
    #sは始点、usedは各頂点が使われたかどうか、dは視点から各頂点への最短距離
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0

    while True:
        #pは最短距離が確定した頂点
        p = -1
        #まだ使われていない頂点のうち距離が最小のものを探す
        for i in range(n):
            if (not used[i]) and (p==-1 or d[i]<d[p]):
                p = i
        
        if p==-1:
            break
        used[p] = True

        for i in range(n):
            d[i] = min(d[i], d[p]+cost[p][i])

    return d

ans=[0]*n
for i in range(n):
    dist=dijkstra(i)
    for j in range(n):
        ans[dist[j]]+=1

for i in range(1,n):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())

a=[[0 for _ in range(n)] for _ in range(n)]
ans=[0 for _ in range(n-1)]

for i in range(n-1):
  for j in range(i+1,n):
    t=i+1
    u=j+1
    a[i][j]=min(abs(u-t),abs(t-x)+1+abs(y-u),abs(t-y)+1+abs(x-u))
    X=a[i][j]
    ans[X-1]+=1
    
for l in ans:
  print(l)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)


# s, t \in V (s < t) に対して、s から t への最短経路を d_min(s, t) とすると、
# d_min(s, t) は、
# d_min(s, t) = min(t - s, abs(x - s) + 1 + abs(t - y))
# で与えられる。
# なので、s, t の全ての組み合わせに対して d_min(s, t) を計算し、条件を満たすような s, t の組を数え上げればよい。


N, X, Y = map(int, input().split())
# 0-index
X -= 1
Y -= 1

# O(N^2)
for k in range(1, N):
    count = 0
    for s in range(N - 1):
        for t in range(s + 1, N):
            dist = min(t - s, abs(X - s) + 1 + abs(t - Y))
            if dist != k:
                continue
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, X, Y = [int(x) for x in input().split()]
result = {x: 0 for x in range(N)}

# 面倒なので0オリジンに修正
X -= 1
Y -= 1

# 全位置から移動できるパターンを幅優先探索で網羅する
for i in range(N):

    queue = deque()
    visited = set()

    # 開始位置と距離を初期値として入れる
    queue.appendleft((i, 0))

    while queue:
        now_pos, distance = queue.pop()

        # 訪れていない場合、その位置に移動するまでの距離に結果を加算
        # 訪問済フラグを立てる
        if not now_pos in visited:
            result[distance] += 1
            visited.add(now_pos)

        # 前、後ろ、X <-> Y の移動を実行
        # すでに訪問済の場合は追加しない
        if now_pos - 1 >= 0:
            if not now_pos - 1 in visited:
                queue.appendleft((now_pos - 1, distance + 1))

        if now_pos + 1 < N:
            if not now_pos + 1 in visited:
                queue.appendleft((now_pos + 1, distance + 1))

        if now_pos == X:
            if not Y in visited:
                queue.appendleft((Y, distance+1))

        if now_pos == Y:
            if not X in visited:
                queue.appendleft((X, distance+1))

for i in range(1, N):
    print(result[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if temp_dis[now] <= depth:
            return
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    # distance = [set() for _ in [0] * N]
    cnt_dis = [0] * N
    for i in range(N):
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            # distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
            cnt_dis[j] += temp_dis.count(j)
    
    # for ans in distance[1:]:
    #     print(len(ans))
    for ans in cnt_dis[1:]:
        print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if temp_dis[now] <= depth:
            return
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    distance = [set() for _ in [0] * N]
    for i in range(N):
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
    
    for ans in distance[1:]:
        print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if temp_dis[now] < depth:
            return
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    distance = [set() for _ in [0] * N]
    for i in range(N):
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
    
    for ans in distance[1:]:
        print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if depth >= N:
            return
        seen[now] = True
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    distance = [set() for _ in [0] * N]
    for i in range(N):
        seen = [False] * N
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
    
    for ans in distance[1:]:
        print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,x,y=map(int,input().split())
x,y=x-1,y-1
e = [[2*10**3+1]*n for _ in range(n)]
for i in range(n):
    e[i][i] = 0

def main():
    for i in range(n):
        s = deque([i])  # サーチstack. 初期条件を設定
        dfs(s, e[i])
    #print(e)
    ans = [0]*n
    for i,ee in enumerate(e):
        for eee in ee[i:]:
            ans[eee] += 1
    for i in ans[1:]:
        print(i)

def dfs(s,e):
    while len(s) > 0:  # len(s) > 0 でループ
        t = s.popleft()
        for i in get_children(t):  # t の子ノードを列挙
            if e[i] != 2*10**3+1 and e[i] < e[t]+1:
                continue
            s.append(i)
            e[i] = min(e[i], e[t] + 1) # 探索済としつつ距離を入れる

def get_children(t):
    if t in (x,y):
        yield y if t == x else x
    if 0 < t:
        yield t-1
    if t < (n-1):
        yield t+1

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, X, Y = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(N - 1):
    G[i].append(i + 1)
    G[N-i-1].append(N - i - 2)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

mind = [[N] * N for _ in range(N)]
todo = deque()
for s in range(N):
    todo.append((0, s))
    done = set()
    while todo:
        d, p = todo.popleft()
        mind[s][p] = min(mind[s][p], d)
        done.add(p)
        for np in G[p]:
            if not np in done:
                todo.append((d + 1, np))

counts = [0] * (N - 1)
for i in range(N - 1):
    for j in range(i + 1, N):
        counts[mind[i][j]-1] += 1
for c in counts:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue
n,x,y=map(int,input().split())
edge=[[i-1,i+1] for i in range(n)]
edge[0],edge[-1]=[1],[n-2]
edge[x-1].append(y-1)
edge[y-1].append(x-1)
inf=10**6
ans=[0]*n
for i in range(n):
    q=queue.deque([i])
    dist=[inf]*n
    dist[i]=1
    while q:
        a=q.pop()
        for e in edge[a]:
            if dist[e]==inf:
                q.appendleft(e)
                dist[e]=dist[a]+1
    for v in dist:
        ans[v-1]+=1
for i in range(n-1):
    print(ans[i+1]//2)

Submission status: Time Limit Exceeded

Solution code:
# # coding=UTF-8
# from collections import deque
# from operator import itemgetter
# from bisect import bisect_left, bisect
# import itertools
# import sys
# import math
# import numpy as np
# import time

n, x, y = map(int, input().split())
tree = [[0] * n for i in range(n)]

for i in range(1, n):
    for j in range(i+1, n+1):
        # if i <= x and j >= y:
        #     tree[i - 1][j - 1] = j-i-(y - x - 1)
        # elif i <= x and j < y:
        #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
        # elif i > x and j >= y:
        #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
        # else:
        #     tree[i - 1][j - 1] = j-i
        tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                    1+abs(j-y), abs(y-i)+1+abs(j-x))

for k in range(1, n):
    ans = 0
    for i in range(n):
        ans += tree[i].count(k)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, x, y = map(int, input().split())
    tree = [[0] * n for i in range(n)]

    for i in range(1, n):
        for j in range(i+1, n+1):
            # if i <= x and j >= y:
            #     tree[i - 1][j - 1] = j-i-(y - x - 1)
            # elif i <= x and j < y:
            #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
            # elif i > x and j >= y:
            #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
            # else:
            #     tree[i - 1][j - 1] = j-i
            tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                     1+abs(j-y), abs(y-i)+1+abs(j-x))

    for k in range(1, n):
        ans = 0
        for i in range(n):
            ans += tree[i].count(k)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
cc = []
for i in range(1,N+1):
  for j in range(i+1,N+1):
    cc.append(min(j-i,abs(X-i)+1+abs(Y-j)))
for i in range(1,N):
  print(cc.count(i))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,x,y=map(int,input().split())
map=[[] for _ in range(n+1)]
for i in range(1,n):
    map[i].append(i+1)
    map[i+1].append(i)
map[x].append(y)
map[y].append(x)

ans=[0]*n

for j in range(1,n+1):
    dict=[-1]*(n+1)
    que=deque()
    que.append(j)
    dict[j]=0
    while que:
        t=que.popleft()
        for k in map[t]:
            if dict[k]==-1:
                dict[k]=dict[t]+1
                que.append(k)
    for l in range(1,n+1):
        ans[dict[l]]+=1
for m in range(1,n):
    print(ans[m]//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[18]:


N,X,Y = map(int, input().split())


# In[19]:


for k in range(1,N):
    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            dist = min(j-i,abs(X-i)+abs(Y-j)+1,abs(Y-i)+abs(X-j)+1)
            if dist == k:
                ans += 1
    print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import queue

N, X, Y = map(int, input().split())
X, Y = X - 1, Y - 1

ans = [0] * (N + 1)

def push(q, dist, index, dist_v):
    if dist[index] != -1:
        return
    q.put(index)
    dist[index] = dist_v

for i in range(N):
    q = queue.Queue()
    dist = [-1] * N
    push(q, dist, i, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v - 1 >= 0: push(q, dist, v - 1, d + 1)
        if v + 1 < N: push(q, dist, v + 1, d + 1)
        if v == X: push(q, dist, Y, d + 1)
        if v == Y: push(q, dist, X, d + 1)
    for j in range(N):
        ans[dist[j]] += 1

for i in range(N):
    ans[i] //= 2

for i in range(1, N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int, input().split())

for k in range(1,N):
    ans = 0
    for l in range(1,N):
        for r in range(l+1, N+1):
            if min(r-l, abs(X-l) + 1 + abs(Y-r)) == k:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            if d[e] < min_dist:
                min_dist = d[e]
            if d[e] == N + 10:
                queue.append(e)
        d[node] = min_dist + 1
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            min_dist = min(d[e], min_dist)
        d[node] = min_dist + 1
        for e in edge[node]:
            if d[e] == N+10:
                queue.append(e)
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')

Submission status: Time Limit Exceeded

Solution code:
# -*= coding: utf-8 -*-
import queue

N, X, Y = map(int, input().split())

q = queue.Queue()

ans = [0] * N

# BFS
for i in range(N):
  # 0 〜 N-1の各頂点からスタート
  
  cost = [-1] * N
  cost[i] = 0
  q.put(i) # 基準とする頂点をノードiにする
  
  while not q.empty():
    
    # 現在のノードのインデックス
    current = q.get()
    
    if current - 1 >= 0 and cost[current - 1] == -1:
      # 1つ前のノードを登録
      
      q.put(current - 1)
      cost[current - 1] = cost[current] + 1
      
    if current + 1 < N and cost[current + 1] == -1:
      # 1つ後ろのノードを登録
      
      q.put(current + 1)
      cost[current + 1] = cost[current] + 1
      
    if current == X - 1 and cost[Y - 1] == -1:
      # XからYへのルートを登録
      
      q.put(Y - 1)
      cost[Y - 1] = cost[current] + 1
    
    if current == Y - 1 and cost[X - 1] == -1:
      # YからXへのルートを登録
      
      q.put(X - 1)
      cost[X - 1] = cost[current] + 1
      
  # この時点でcostにはノードiから各ノードへの最小コストが格納されている
  
  #print(cost)
  for j in range(N):
    ans[cost[j]] += 1

for i in range(1, N):
  print(ans[i]//2) # ノードA→Bと、逆向きのB→Aが、両方カウントされているので2分の1する

Submission status: Time Limit Exceeded

Solution code:
import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,deque
def bfs(G,s,N):
    dist=[-1]*(N+1)
    d=deque()
    dist[s]=0
    d.append(s)
    while(len(d)!=0):
        v=d[0]
        d.popleft()
        for nv in G[v]:
            if(dist[nv]!=-1):
                continue
            #発見した地点への操作
            dist[nv]=dist[v]+1
            d.append(nv)
            #ここまで
    return dist

N,X,Y=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(1,N):
    G[i].append(i+1)
    G[i+1].append(i)
G[X].append(Y);G[Y].append(X)
Count=[0]*(N+1)
for i in range(1,N+1):
    li=bfs(G,i,N)
    c=Counter(li)
    for i in range(1,N+1):
        Count[i]+=c[i]
for i in range(1,N):
    print(Count[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import chain
from collections import Counter

def floyd_warshall(V, dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]                # dist は頂点 k までを経由した場合の最短距離。dist[i][k]は k を経由することは無いので、dist[i][k]は k ステップ目で更新されることはない。
                                                                        # よって、min の中身は全て k-1 ステップ目の情報で構成されており、漸化式となっている。
    return dist

##############################
V, X, Y = map(int, input().split())                                        # V:頂点数　E:辺の数

INF = float("inf")                                                      # 10**18 にすると、負のコストがある場合に少し面倒になる

dist = [[INF] * V for _ in range(V)]                                    # 辺が存在しない事をコスト無限大で表現
for k in range(V-1):
    i,j,weight = k, k+1, 1
    # i -= 1                                                            # 番号のデクリメントが必要な場合、コメントアウトを消す
    # j -= 1
    dist[i][j] = weight
    dist[j][i] = weight                                               # 無向グラフの場合はコメントアウトを消す
for i in range(V):
    dist[i][i] = 0                                                      # 自身のところに行くコストは０

dist[X-1][Y-1] = 1
dist[Y-1][X-1] = 1

d = floyd_warshall(V, dist)                                                # 各点間の距離が隣接行列の形で与えられる

res = Counter(chain.from_iterable(d))

for i in range(1,V):
    print(res.get(i,0)//2)

Submission status: Time Limit Exceeded

Solution code:
import math
nums = [int(i) for i in input().split()]
n = nums[0]
x = nums[1]
y = nums[2]
res = {}
for i in range(1, n):
    res[i] = 0
for i in range(1, n+1):
    for j in range(i+1, n+1):
        dis = j - i
        disI = min(abs(i-x), abs(i-y))
        disJ = min(abs(j-x), abs(j-y))
        dis = min(dis, disI+disJ+1)
        res[dis] += 1
for i in range(1, n):
    print(res[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
G = np.zeros((N, N), dtype=int)
for i in range(N):
    for j in range(i+1, N):
        G[i][j] = min(j - i, abs(X - i) + 1 + abs(Y - j))
for cnt in range(1, N):
    print(np.sum(G == cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, X, Y = map(int, input().split())

G = np.full((N, N), np.inf, dtype=float)
for i in range(N - 1):
    G[i][i + 1] = 1
    G[i + 1][i] = 1
G[X - 1][Y - 1] = 1
G[Y - 1][X - 1] = 1

G = shortest_path(G)
for cnt in range(1, N):
    print(np.sum(G == cnt) // 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, X, Y = map(int, input().split())

G = np.full((N, N), np.inf, dtype=float)
for i in range(N - 1):
    G[i][i + 1] = 1
    G[i + 1][i] = 1
G[X - 1][Y - 1] = 1
G[Y - 1][X - 1] = 1

G = shortest_path(G, method='D')
for cnt in range(1, N):
    print(np.sum(G == cnt) // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

ans = [0]*n
for j in range(1,n):
    dist = bfs(j,graph)
    for k in range(1,n):
        ans[k] += dist.count(k)
    
for x in range(1,n):
    print(ans[x])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

  
for k in range(1,n):
    ans = 0
    for j in range(1,n):
        dist = bfs(j,graph)
        ans += dist.count(k)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

N,X,Y=map(int, input().split())
INF=100000
d = [[INF if i!=j else 0 for i in range(N) ] for j in range(N)]
d=np.array(d)
d[X-1,Y-1]=d[Y-1,X-1]=1
for k in range(N):
  for i in range(N):
    for j in range(N):
      if abs(i-j)==1:d[i][j] =d[j][i]=1
      d[i][j] = min(d[i][j], d[i][k]+d[k][j])

unique, counts = np.unique(d, return_counts=True)
count = dict(zip(unique, counts))
for i in range(1,N):
  if count.get(i):print(count[i]//2)
  else: print(0)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
INFTY=sys.maxsize

def readinput():
    n,x,y=list(map(int,input().split()))
    return n,x,y

def dijkstra(s,n,nList):
    '''優先度付きキューを使用したダイクストラ法

    パラメーター
    s: 始点
    n: 頂点の数
    nList: [ 
        [vertex1, cost1], [vertex2, cost2], ...
        [vertex1, cost1], [vertex2, cost2], ...
        ...
    ]

    返り値
    d: 始点sから各頂点vまでの最短経路上の辺の重みの総和d[v]のリスト
    '''

    WHITE=0
    GRAY=1
    BLACK=2
    color=[WHITE]*n
    d=[INFTY]*n

    HQ=[]

    d[s]=0
    heappush(HQ,(d[s],s))

    while(len(HQ)>0):
        #print(HQ)
        du,u=heappop(HQ)
        color[u]=BLACK

        if d[u]<du:
            continue

        for v in nList[u]:
            vw=1
            if color[v]!=BLACK:
                if d[u] + vw < d[v]:
                    d[v] = d[u] + vw
                    color[v]=GRAY
                    heappush(HQ, (d[v], v))
    return d

def main(n,x,y):
    nList=[]
    #nList.append([])
    nList.append([1])
    for i in range(1,n-1):
        nList.append([i-1,i+1])
    nList.append([n-2])
    nList[x-1].append(y-1)
    nList[y-1].append(x-1)
    #print(nList)

    dList=[]
    for i in range(n):
        dList.append(dijkstra(i,n,nList))
    #print(dList)
    
    hist=[0]*n
    for i in range(n-1):
        for j in range(i+1,n):
            hist[dList[i][j]]+=1
    
    for i in range(1,n):
        print(hist[i])


if __name__=='__main__':
    n,x,y=readinput()
    main(n,x,y)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix

N, X, Y = [int(_) for _ in input().split()]
G = lil_matrix((N, N))
G[X - 1, Y - 1] = 1
for i in range(N - 1):
    G[i, i + 1] = 1
D = floyd_warshall(G, directed=False)
for i in range(1, N):
    print(np.sum(D == i) // 2)