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:
#５回目、2020-0612
#幅優先探索
def bfs(u):
    dq =deque()
    passed =set([u])
    for i in range(1,N+1): #全頂点を始点としてBSFで距離
        dq.append(i)
        dist[(i,i)] =0   
        while dq:
            now =dq.popleft()
            for next in connection[now]:
                if next not in passed and i !=next:
                    dist[(i,next)] =dist[(i,now)] +1
                    ans[dist[(i,next)]].append((i,next))
                    dq.append(next)
                    passed.add(next)
        passed.clear()

    return dist

#初期入力
from collections import deque 
N, x, y = map(int, input().split())

# 構造
connection ={i:set() for i in range(1,N+1)}
for i in range(1,N):
    connection[i  ].add(i+1)
    connection[i+1].add(i)
connection[x].add(y)
connection[y].add(x)

#始点からの距離をBFS
ans ={(i):[] for i in range(0,N) }
dist ={(i,j):None for i in range(1,N) for j in range(i,N+1)}
bfs(1)

#答え出力
for i in range(1,N):        
    print(len(ans[i])//2)

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)
for i in range(1, n):
    G[i].append(i-1)
x -= 1
y -= 1
G[x].append(y)
G[y].append(x)

# iとjの最短距離を返す
def bfs(i, j):
    i -= 1
    j -= 1
    q = deque()
    seen = [False] * n
    dist = [-1] * n

    q.append(i)
    seen[i] = True
    dist[i] = 0
    while len(q) > 0:
        now_v = q.popleft()
        for new_v in G[now_v]:
            if seen[new_v] is True:
                continue
            q.append(new_v)
            seen[new_v] = True
            dist[new_v] = dist[now_v] + 1
            if new_v == j:
                return dist[j]

cnt = [0] * (n-1)
for i in range(n-1):
    for j in range(i+1, n):
        cnt[bfs(i, j)-1] += 1

for ans in cnt:
    print(ans)

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)
for i in range(1, n):
    G[i].append(i-1)
x -= 1
y -= 1
G[x].append(y)
G[y].append(x)

# iとjの最短距離を返す
def bfs(i, j):
    i -= 1
    j -= 1
    q = deque()
    seen = [False] * n
    dist = [-1] * n

    q.append(i)
    seen[i] = True
    dist[i] = 0
    while len(q) > 0:
        now_v = q.popleft()
        for new_v in G[now_v]:
            if seen[new_v] is True:
                continue
            q.append(new_v)
            seen[new_v] = True
            dist[new_v] = dist[now_v] + 1
    return dist[j]

cnt = [0] * (n-1)
for i in range(n-1):
    for j in range(i+1, n):
        cnt[bfs(i, j)-1] += 1

for ans in cnt:
    print(ans)

Submission status: Time Limit Exceeded

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

ans = [0]*(N-1)

for i in range(N):
    visited = [0]*N
    dist = [0]*N
    q = deque([i])#i番目のノードを根とする探索
    visited[i] = 1
    while q:
        now = q.popleft()
        for connection in edge[now]:
            if visited[connection]:
                dist[connection] = min(dist[connection],dist[now]+1)
            else:
                visited[connection] = 1
                dist[connection] = dist[now] + 1
                q.append(connection)
    for d in dist:
        if d == 0:
            continue
        ans[d-1] += 1
ans = list(map(lambda x: x//2,ans))
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
from collections import Counter
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, X, Y = map(int, input().split())

    v1 = [i for i in range(1, N)] + [X]
    v2 = [i for i in range(2, N + 1)] + [Y]
    d = [1] * N
    csr = csr_matrix((d, (v1, v2)), (N + 1, N + 1))
    g = floyd_warshall(csr, directed=False)
    dist = []
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            dist.append(int(g[i][j]))
    ans = Counter(dist)
    for i in range(1, N):
        print(ans[i])


main()

Submission status: Time Limit Exceeded

Solution code:
#4回目、2020-0609 BSFやりかけたが・・・
#幅優先探索
def bfs(u):
    dist ={i:None for i in range(1,N+1)}
    dist[u] =0   
    dq =deque()
    dq.append(u)
    passed =set([u])
    #for i in range(1,N+1): #全頂点を始点としてBSFで距離
     #   dq.append(i)
    while dq:
        now =dq.popleft()
        for next in connection[now]:
            if next not in passed:
                dist[next] =dist[now] +1
                dq.append(next)
                passed.add(next)
    return dist

#初期入力
from collections import deque 
N, x, y = map(int, input().split())

# 構造
connection ={i:set() for i in range(1,N+1)}
for i in range(1,N):
    connection[i  ].add(i+1)
    connection[i+1].add(i)
connection[x].add(y)
connection[y].add(x)

#始点からの距離をBFS
#ans ={(i,j):[] for i in range(1,N+1) for j in range(1,N+1)}
ans ={(i):[] for i in range(0,N) }
for i in range(1,N+1): # i=始点
    d=bfs(i)
    for j,v in d.items(): #j=各頂点、v=始点から各頂点の距離
        if i <j:
            ans[v].append((i,j)) 
        #ans[i,j].append(v) 
for i in range(1,N):        
    print(len(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n, x, y = map(int, input().split())
x -= 1
y -= 1
 
def calc(i, j, x, y):
    mindist = abs(j - i)
    mindist = min(mindist, abs(x - i) + 1 + abs(y - j))
    mindist = min(mindist, abs(y - i) + 1 + abs(x - j))
    return mindist
 
result = [0 for i in range(n)]
for i in range(n):
    for j in range(n):
        if i == j :
            continue
        k = calc(i, j, x, y)       
        result[k] += 1
 
for i in range(1, n):
    print(result[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

def calc(i, j, x, y):
    mindist = abs(j - i)
    mindist = min(mindist, abs(x - i) + 1 + abs(y - j))
    mindist = min(mindist, abs(y - i) + 1 + abs(x - j))
    return mindist

result = [0 for i in range(n)]
dist = np.zeros((n, n))
for i in range(n):
    for j in range(n):
        if i == j :
            continue
        k = calc(i, j, x, y)       
        dist[i][j] = k
        result[k] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
l = [0] * N
for i in range(1,N):
    for j in range(i+1,N+1):
        #i j
        ij = j - i
        #i x y j
        ixyj = abs(X - i) + 1+ abs(Y -j)
        #i y x j
        iyxj = abs(Y - i) + 1 + abs(X- j)
        length = min(min(ij,ixyj),iyxj)
        l[length] +=1
for i in range(1,N):
    print(l[i])

Submission status: Time Limit Exceeded

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

G=[[i+1] for i in range(N)]
G[N-1].pop()
for i in range(1,N):
    G[i].append(i-1)
G[X-1].append(Y-1)
G[Y-1].append(X-1)

from collections import deque

q=deque([])
cnt=[0]*N

for n in range(N-1):
    seen=[0]*N
    q.append([n,0])
    seen[n]=1
    while q:
        x,c=q.popleft()
        if c>=N-1:continue
        for g in G[x]:
            if seen[g]==0:
                q.append([g,c+1])
                seen[g]=1
                if n<g:
                    cnt[c+1]+=1
for i in range(1,N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, x, y = list(map(int, input().split()))
m = np.zeros((n,n))
m[x-1,y-1] = 1
for i in range(n):
    for j in range(i, n):
        m[i,j] = min(j-i, abs((x-1)-i)+abs((y-1)-j)+1)

for i in range(n-1):
    print(int(np.count_nonzero(m==i+1)))

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                a = abs(j + 1 - i)
                if a == 1:
                    answerList[1] = answerList[1] + 1
                    continue
                calculateList = [a,
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = [0] * 9999

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answerList[min(calculateList)] = answerList[
                                                     min(calculateList)] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    for j in range(N[0]):
        if j + 1 > i > 0:
            calculateList = [abs(j + 1 - i),
                             abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                             abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
            answerList[min(calculateList)] = answerList[min(calculateList)] + 1

for i in range(N[0] - 1):
    print(answerList[i+1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]+1):
    answerList.append(0)

for i in range(N[0]):
    for j in range(N[0]):
        if j + 1 > i > 0:
            calculateList = [abs(j + 1 - i),
                             abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                             abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
            answerList[min(calculateList)] = answerList[min(calculateList)] + 1

for i in range(N[0] - 1):
    print(answerList[i+1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]+1):
    answerList.append(0)

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(N[1] - i) + 1 + abs(j - N[2]),
                             abs(N[2] - i) + 1 + abs(j - N[1])]
            answerList[min(calculateList)] = answerList[min(calculateList)] + 1

for i in range(N[0] - 1):
    print(answerList[i+1])

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(N[1] - i) + 1 + abs(j - N[2]),
                             abs(N[2] - i) + 1 + abs(j - N[1])]
            answerList.append(min(calculateList))

for i in range(N[0] - 1):
    print(answerList.count(i + 1))

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(abs(N[1] - i) + + 1 + abs(j - N[2])),
                             abs(abs(N[2] - i) + + 1 + abs(j - N[1]))]
            answerList.append(min(calculateList))

for i in range(N[0] - 1):
    print(answerList.count(i + 1))

Submission status: Time Limit Exceeded

Solution code:
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    count = 0
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(abs(N[1] - i) + + 1 + abs(j - N[2])),
                             abs(abs(N[2] - i) + + 1 + abs(j - N[1]))]

            answerList.append(min(calculateList))

for i in range(N[0] - 1):
    print(answerList.count(i + 1))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split(' '))
dist = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dist[X][Y] = 1
res = [0 for i in range(N + 10)]
for i in range(1, N):
  for j in range(i + 1, N + 1):
    dist[i][j] = min(j - i, abs(j - X) + 1 + abs(i - Y), abs(j - Y) + 1 + abs(i - X))
    res[dist[i][j]] += 1
for i in range(1, N):
  print(res[i])

Submission status: Time Limit Exceeded

Solution code:
def m():
    N, X, Y = map(int, input().split())
    ans = [0] * (N+1)
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            p = min(abs(j - i), abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j))
            ans[p] += 1
    for a in range(1, N):
        print(ans[a]//2)

m()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n, x, y = map(int, input().split())
cost = [[] for i in range(n)] 
for i in range(n):
    for j in range(n):
        cost[i].append([abs(j - i), j])
# cost[x - 1][y - 1] = 1
cost[x - 1].append([1, y - 1])
cost[y - 1].append([1, x - 1])
# cost[y - 1][x - 1] = 1
# print(cost)
ans = [0 for i in range(1, n)]
for i in range(n):
    d = dijkstra_heap(i, cost, n)
    # print("d =", d)
    for j in d:
        if j != 0:
            ans[j - 1] += 1
for i in ans:
    print(i // 2)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int,input().split())
d = {}
for i in range(1, n+1):
    for j in range(i+1, n+1):
        l = min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        d[l] = 1 if l not in d else d[l] + 1
for i in range(1, n):
    if i in d:
        print(d[i])
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,X,Y = map(int,input().split())
G = dict()
for i in range(0,N):
    G[i] = []
for i in range(0,N-1):
    G[i].append(i+1)
    G[i+1].append(i)
G[X-1].append(Y-1)
G[Y-1].append(X-1)
ans = [0 for _ in range(N)]
def bfs(v,G,queue,dist):
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
for k in range(0,N):
    dist = [-1 for _ in range(N)]
    dist[k] = 0
    seen = [False for _ in range(N)]
    queue = []
    bfs(k,G,queue,dist)
    for j in range(1,N):
        a = dist.count(j)
        ans[j-1] += a
for j in range(1,N):
    print(ans[j-1]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

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

G = [[] for i in range(N)]
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)

for i in range(N - 1):
  G[i].append(i + 1)
  G[i + 1].append(i)
  
ans = [0 for i in range(N)]

from collections import deque
for st in range(N):
  q = deque([[st,0,-1]])
  visited = set()
  while q:
    v,dist,parent = q.popleft()
    if v in visited:
      continue
    visited.add(v)
    ans[dist] += 1
    for child in G[v]:
      if child == parent:
        continue
      q.append([child, dist + 1, v])
    
for i in range(1, N):
  print(ans[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

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

G = [[] for i in range(N)]
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)

for i in range(N - 1):
  G[i].append(i + 1)
  G[i + 1].append(i)
  
ans = [0 for i in range(N)]

from collections import deque
for st in range(N):
  q = deque([[st,0]])
  visited = set()
  while q:
    v,dist = q.popleft()
    if v in visited:
      continue
    visited.add(v)
    ans[dist] += 1
    for child in G[v]:
      q.append([child, dist + 1])
    
for i in range(1, N):
  print(ans[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


def solve(N, X, Y):
    ans = [0] * (N)

    G = [[] for _ 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)

    def dfs(vertex):
        nears = [float('inf')] * (N + 1)
        depth = 0
        que = [[depth, vertex]]
        while que:
            d, v = heappop(que)
            if d < nears[v]:
                nears[v] = d
                for g in G[v]:
                    heappush(que, [d + 1, g])
        return nears

    for i in range(1, N):
        # dfs
        nears = dfs(i)
        # print(nears)
        for j in range(i + 1, N + 1):
            ans[nears[j]] += 1

    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    N, X, Y = map(int, input().split())
    solve(N, X, Y)

Submission status: Time Limit Exceeded

Solution code:
import sys
# from collections import defaultdict
# from collections import Counter
# from queue import PriorityQueue
# sys.setrecursionlimit(2000000)

def distance(X, Y, start, goal):
    ans = float('inf')

    tmp = goal - start
    if tmp < ans:
        ans = tmp

    # start ~ X ~ Y ~ goal,
    tmp = abs(X - start) + 1 + abs(goal - Y)
    if tmp < ans:
        ans = tmp

    # start ~ Y ~ X ~ goal
    tmp = abs(Y - start) + 1 + abs(goal - X)
    if tmp < ans:
        ans = tmp

    return ans

#     # 短絡パスを使える場合
#     if start <= X and Y <= goal

#     # 短絡パスを使えないならば、普通に距離を計算
#     if X < start:
#         return goal - start

#     # 短絡パスを使えても、隣のパスへの距離は1
#     if goal - start == 1:
#         return 1

#     # 短絡パスより手前だと使えない
#     if goal < Y:
#         return goal - start



    # return goal - start - 1

def main():
    # N = int(input())

    N, X, Y = [int(s) for s in input().split()]

    distance_dict = {}
    for i in range(1, N+1):
        for j in range(i + 1, N+1):
            d = distance(X, Y, i, j)
            # sys.stderr.write('{} to {} : d = {}\n'.format(i, j, d))
            # ditance_dict[(i, j)] = d
            if d in distance_dict:
                distance_dict[d] += 1
            else:
                distance_dict[d] = 1

    for k in range(1, N):
        # print(str(distance_dict[k]))
        if k in distance_dict:
            print(distance_dict[k])
        else:
            print('0')
    # As = []
    # Bs = []
    # for i in range(N):
    #     A, B = [int(s) for s in input().split()]
    #     As.append(A)
    #     Bs.append(B)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
# from collections import Counter
# from queue import PriorityQueue
# sys.setrecursionlimit(2000000)

def distance(X, Y, start, goal):
    ans = float('inf')

    tmp = goal - start
    if tmp < ans:
        ans = tmp

    # start ~ X ~ Y ~ goal,
    tmp = abs(X - start) + 1 + abs(goal - Y)
    if tmp < ans:
        ans = tmp

    # start ~ Y ~ X ~ goal
    tmp = abs(Y - start) + 1 + abs(goal - X)
    if tmp < ans:
        ans = tmp

    return ans

#     # 短絡パスを使える場合
#     if start <= X and Y <= goal

#     # 短絡パスを使えないならば、普通に距離を計算
#     if X < start:
#         return goal - start

#     # 短絡パスを使えても、隣のパスへの距離は1
#     if goal - start == 1:
#         return 1

#     # 短絡パスより手前だと使えない
#     if goal < Y:
#         return goal - start



    # return goal - start - 1

def main():
    # N = int(input())

    N, X, Y = [int(s) for s in input().split()]

    distance_dict = defaultdict(int)
    for i in range(1, N+1):
        for j in range(i + 1, N+1):
            d = distance(X, Y, i, j)
            # sys.stderr.write('{} to {} : d = {}\n'.format(i, j, d))
            # ditance_dict[(i, j)] = d
            distance_dict[d] += 1

    for k in range(1, N):
        # print(str(distance_dict[k]))
        print(distance_dict[k])

    # As = []
    # Bs = []
    # for i in range(N):
    #     A, B = [int(s) for s in input().split()]
    #     As.append(A)
    #     Bs.append(B)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
# from collections import Counter
# from queue import PriorityQueue
# sys.setrecursionlimit(2000000)

def distance(X, Y, start, goal):
    lst = [
        goal - start,

        # start ~ X ~ Y ~ goal,
        abs(X - start) + 1 + abs(goal - Y),

        # start ~ Y ~ X ~ goal
        abs(Y - start) + 1 + abs(goal - X),
    ]
    return min(lst)

#     # 短絡パスを使える場合
#     if start <= X and Y <= goal

#     # 短絡パスを使えないならば、普通に距離を計算
#     if X < start:
#         return goal - start

#     # 短絡パスを使えても、隣のパスへの距離は1
#     if goal - start == 1:
#         return 1

#     # 短絡パスより手前だと使えない
#     if goal < Y:
#         return goal - start



    # return goal - start - 1

def main():
    # N = int(input())

    N, X, Y = [int(s) for s in input().split()]

    distance_dict = defaultdict(list)
    for i in range(1, N+1):
        for j in range(i + 1, N+1):
            d = distance(X, Y, i, j)
            # sys.stderr.write('{} to {} : d = {}\n'.format(i, j, d))
            # ditance_dict[(i, j)] = d
            distance_dict[d].append((i, j))

    for k in range(1, N):
        # print(str(distance_dict[k]))
        print(len(distance_dict[k]))

    # As = []
    # Bs = []
    # for i in range(N):
    #     A, B = [int(s) for s in input().split()]
    #     As.append(A)
    #     Bs.append(B)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

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

adj = [[] for i in range(n)]

adj[x-1].append(y-1)
adj[y-1].append(x-1)

for i in range(n-1):
    adj[i].append(i+1) 
    adj[i+1].append(i)
        
ans = [0 for _ in range(n+1)]

def bfs(start):
    inf = 1001001001
    q = queue.Queue()
    q.put(start)
    dist = [inf]*n
    dist[start] = 0
    
    while not q.empty():
        v = q.get()

        for i in adj[v]:
            if dist[i] == inf:
                dist[i] = dist[v] + 1
                q.put(i)

    for i in range(n):
        ans[dist[i]] += 1

for i in range(n):
    bfs(i)

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

Submission status: Time Limit Exceeded

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

list =[]
for i in range(n):
  for j in range(i):
    b = i+1
    a = j+1
    if a<=x and b>=y:
      list.append(b-y+x-a+1)
    elif a>x and b>=y:
      d =min(a-x+1,y-a)
      list.append(d+b-y)
    elif a<=x and b<y:
      d =min(b-x,y-b+1)
      list.append(x-a+d)
    elif a>x and b<y:
      list.append(min(b-a,y-b+a-x+1))
    else:
      list.append(b-a)
for i in range(n-1):
  print(list.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

inf = 100100100
x -= 1
y -= 1

ans = [0] * n

for i in range(n):
    dist = [inf] * n
    queue = deque()
    queue.append(i)
    dist[i] = 0
    while queue:
        current = queue.popleft()
        d = dist[current]

        if current - 1 >= 0 and dist[current - 1] == inf:
            queue.append(current - 1)
            dist[current - 1] = d + 1
        if current + 1 < n and dist[current + 1] == inf:
            queue.append(current + 1)
            dist[current + 1] = d + 1
        if current == x and dist[y] == inf:
            queue.append(y)
            dist[y] = d + 1
        if current == y and dist[x] == inf:
            queue.append(x)
            dist[x] = d + 1

    for j in range(n):
        ans[dist[j]] += 1

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

Submission status: Time Limit Exceeded

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

g = [[] for i in range(n)]
for i in range(n):
    if i != 0:
        g[i].append(i-1)
    if i != n-1:
        g[i].append(i+1)
g[x-1].append(y-1)
g[y-1].append(x-1)


inf = 10**5
dp = [[inf for i in range(n)] for j in range(n)]
todo = collections.deque()

for i in range(n):
    dp[i][i] = 0
    for j in g[i]:
        todo.append(j)
    while len(todo) > 0:
        now = todo.popleft()
        leng = inf
        for j in g[now]:
            if dp[i][j] == inf:
                todo.append(j)
            else:
                tem = dp[i][j] + 1
                if tem < leng:
                    leng = tem
        dp[i][now] = leng

for i in range(1,n):
    ans = 0
    for j in range(n):
        for k in range(j+1,n):
                if dp[j][k] == i:
                    ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

g = [[] for i in range(n)]
for i in range(n):
    if i != 0:
        g[i].append(i-1)
    if i != n-1:
        g[i].append(i+1)
g[x-1].append(y-1)
g[y-1].append(x-1)

inf = 10**5
dp = [[inf for i in range(n)] for j in range(n)]
todo = collections.deque()

for i in range(n):
    dp[i][i] = 0
    for j in g[i]:
        todo.append(j)
    while len(todo) > 0:
        now = todo.popleft()
        leng = inf
        for j in g[now]:
            if dp[i][j] == inf:
                todo.append(j)
            else:
                tem = dp[i][j] + 1
                if tem < leng:
                    leng = tem
        dp[i][now] = leng

for i in range(1,n):
    ans = 0
    for j in range(n):
        for k in range(n):
            if j < k:
                if dp[j][k] == i:
                    ans += 1
    print(ans)