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:
import sys
import queue
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        num=0
        
        Tovis=[start]
        kyori[start]=0
        visited=[]
        
        while Tovis:
            nex=Tovis.pop(0)
            
            visited.append(nex)
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    if v in visited:
                        continue
                    if v in Tovis:
                        continue
                    Tovis.append(v)
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue


def main():
    
    input=sys.stdin.readline
    n,x,y=map(int,input().split())

    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1

    
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*n#queueに入ったかを記録する
        Tovis=queue.Queue()#探索待ちの点を入れるキュー
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0        
        while Tovis.empty()==False:            
            nex=Tovis.get()            
            for v in range(n):                
                tmp=graph[nex][v]
                if tmp!=-1:                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    
    for i in range(n):
        bfs(i,edge,step)
        
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


from collections import deque
class Graph:
    edges = {}

    def append_edge(self, sv, ev, weight = 1):
        if sv in self.edges:
            self.edges[sv].append((ev, weight))
        else:
            self.edges[sv] = [(ev, weight)]

    def bfs(self, sv):
        dist = np.full(len(self.edges.keys()), -1)
        q = deque([])   # キュー
        q.append(sv)
        dist[sv] = 0
        connect_vtxs = []
        while len(q) > 0:
            p = q.popleft()     # キュー取りだし（先頭）
            connect_vtxs.append(p)
            for (ev, w) in self.edges[p]:
                if dist[ev] != -1:
                    continue
                q.append(ev)    # キュー追加
                dist[ev] = dist[p] + 1
        return dist, connect_vtxs

N, X, Y = list(map(int, input().split()))
g = Graph()
for i in range(N - 1):
    g.append_edge(i, i + 1)
    g.append_edge(i + 1, i)
g.append_edge(X - 1, Y - 1)
g.append_edge(Y - 1, X - 1)
dist_cnt = np.zeros(N)
for sv in range(N):
    dist, connect_vtxs = g.bfs(sv)
    for j in range(dist.shape[0]):
        if dist[j] == -1: continue
        dist_cnt[dist[j]] += 1

for i in range(N-1):
    print(int(dist_cnt[i+1]/2))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

import numpy as np
def main():
    #t1=time.time()
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=np.array([0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)])
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    np.array(edge)
    #t2=time.time()
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*n#queueに入ったかを記録する
        Tovis=queue.Queue()#探索待ちの点を入れるキュー
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0        
        while Tovis.empty()==False:            
            nex=Tovis.get()            
            for v in range(n):                
                tmp=graph[nex][v]
                if tmp!=-1:                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    
    for i in range(n):
        bfs(i,edge,step)
        
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

import numpy as np
def main():
    #t1=time.time()
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    np.array(edge)
    #t2=time.time()
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*n#queueに入ったかを記録する
        Tovis=queue.Queue()#探索待ちの点を入れるキュー
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0        
        while Tovis.empty()==False:            
            nex=Tovis.get()            
            for v in range(n):                
                tmp=graph[nex][v]
                if tmp!=-1:                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    
    for i in range(n):
        bfs(i,edge,step)
        
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, x, y = map(int, input().split())
graph = dict()
for i in range(1, n+1):
    if i not in graph.keys():
        graph[i] = set()
    if i < n:
        graph[i].add(i+1)
    if i > 1:
        graph[i].add(i-1)
graph[x].add(y)
graph[y].add(x)
dist = [[]]
def bfs(source):
    q = deque()
    q.append(source)
    d = [pow(10, 4)] * (n+1)
    d[source] = 0
    vis = [0] * (n+1)
    while len(q):
        temp = q.popleft()
        for i in graph[temp]:
            if not vis[i]:
                q.append(i)
                vis[i] = 1
            d[i] = min(d[temp]+1, d[i])
    dist.append(d)
for i in range(1, n+1):
    bfs(i)
dp = dict()
for i in range(1, n):
    for j in range(i+1, n+1):
        if dist[i][j] not in dp.keys():
            dp[dist[i][j]] = 0
        dp[dist[i][j]] += 1
for i in range(1, n):
    if i not in dp.keys():
        print(0)
    else:
        print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
import time
import numpy as np
def main():
    #t1=time.time()
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    np.array(edge)
    #t2=time.time()
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*n#queueに入ったかを記録する
        Tovis=queue.Queue()#探索待ちの点を入れるキュー
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0        
        while Tovis.empty()==False:            
            nex=Tovis.get()            
            for v in range(n):                
                tmp=graph[nex][v]
                if tmp!=-1:                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    
    for i in range(n):
        bfs(i,edge,step)
        
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*n#queueに入ったかを記録する
        Tovis=queue.Queue()#探索待ちの点を入れるキュー
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0        
        while Tovis.empty()==False:            
            nex=Tovis.get()            
            for v in range(n):                
                tmp=graph[nex][v]
                if tmp!=-1:                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
from collections import Counter
N,X,Y = [int(x) for x in stdin.readline().rstrip().split()] 
ans = Counter()

for k in range(1,N+1):
    dist = [0] + [10**9]*(N)
    visited = [False for i in range(N+1)]
    visit_p = deque()
    visit_p.append((k,0))

    while visit_p:
        #print(visit_p)
        node,cnt = visit_p.popleft()
        dist[node] = min(cnt,dist[node])

        if node == X:
            #print(node,cnt,"s")
            if not visited[Y]:
                visit_p.append((Y,cnt+1))
                visited[Y] = True

        if node == Y:
            #print(node,cnt,"s")
            if not visited[X]:
            #ans[cnt+1] += 1
                visit_p.append((X,cnt+1))
                visited[X] = True
        #print(visit_p,"e")   
        for d in [-1,1]:
            if node + d < 1 or node + d > N:
                continue
            if visited[node+d]:
                continue
            #print(node+d,cnt,"e")
            #ans[cnt+1] += 1
            visited[node+d] = True
            visit_p.append((node+d,cnt+1))
        
    ans += Counter(dist)
    
for i in range(1,N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

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

X-=1
Y-=1

dist={}

for k in range(N):
    dist[k]=0

for i in range(N):
    for j in range(N):
        dist[(min(abs(i-j),abs(i-Y)+abs(X-j)+1,abs(i-X)+abs(Y-j)+1))]+=1
for d in range(1,N):
    print(dist[d]//2)

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(n):
  for j in range(i+1,n):
    nagasa=min(abs(j-i),(abs(x-(i+1))+1+abs((j+1)-y)),(abs(y-(i+1))+1+abs((j+1)-x)))
    #print(i,j,nagasa)
    ans[nagasa-1]+=1
for i in range(n-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*len(graph[0])
        Tovis=queue.Queue()
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0
        
        while Tovis.empty()!=True:
            #print(que_check)
            
            nex=Tovis.get()
            #print(nex)
            
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        que_check=[0]*len(graph[0])
        Tovis=queue.Queue()
        Tovis.put(start)
        que_check[start]=1
        kyori[start]=0
        
        while Tovis.empty()!=True:
            #print(que_check)
            
            nex=Tovis.get()
            #print(nex)
            que_check[nex]=1
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    
                    if que_check[v]==1:
                        continue
                    Tovis.put(v)
                    que_check[v]=1
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Ndmin=[0]*(N-1)
for i in range(1,N):
    tmp=deque([i])
    dmin=deque([0])
    Dmin=[10000]*(N)
    while tmp:
        E=tmp.popleft()
        d=dmin.popleft()
        Dmin[E-1]=min(d,Dmin[E-1])
        if E<N:
            if d+1<Dmin[E]:
                tmp.append(E+1)
                dmin.append(d+1)
        if E>1:
            if d+1<Dmin[E-2]:
                tmp.append(E-1)
                dmin.append(d+1)
        if E==X and d+1<Dmin[Y-1]:
            tmp.append(Y)
            dmin.append(d+1)
        if E==Y and d+1<Dmin[X-1]:
            tmp.append(X)
            dmin.append(d+1)
        
    for ii in range(i,N):
        Ndmin[Dmin[ii]-1]+=1

for i in range(N-1):
    print(Ndmin[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
import numpy as np
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        num=0
        
        Tovis=[start]
        kyori[start]=0
        visited=[]
        
        while Tovis:
            nex=Tovis.pop(-1)
            
            visited.append(nex)
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    if v in visited:
                        continue
                    if v in Tovis:
                        continue
                    Tovis.reverse()
                    Tovis.append(v)
                    Tovis.reverse()
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cnt = [0] * (N)
for i in range(1, N+1):
  for j in range(i+1, N+1):
    temp = min(abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x))
    cnt[min(abs(j-i), temp)] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# D - Line++
from collections import deque

INF = 1001001001

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

for i in range(n):
    dist = [INF]*n
    q = deque()
    dist[i] = 0
    q.append(i)
    
    while len(q)>0:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0:
            if dist[v-1]==INF:
                q.append(v-1)
                dist[v-1]=d+1
        if v+1 < n:
            if dist[v+1]==INF:
                q.append(v+1)
                dist[v+1]=d+1
        if v==x:
            if dist[y]==INF:
                q.append(y)
                dist[y]=d+1
        if v==y:
            if dist[x]==INF:
                q.append(x)
                dist[x]=d+1
    for d in dist:
        if d!=0 and d!=INF:
            ans[d] += 1

for a in ans[1:]:
    print(int(a//2))

Submission status: Time Limit Exceeded

Solution code:
# D - Line++
from collections import deque

INF = 1001001001

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

for i in range(n):
    dist = [INF]*n
    q = deque()
    dist[i] = 0
    q.append(i)
    
    while len(q)>0:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0 and dist[v-1]==INF:
            q.append(v-1)
            dist[v-1]=d+1
        if v+1 < n and dist[v+1]==INF:
            q.append(v+1)
            dist[v+1]=d+1
        if v==x and dist[y]==INF:
            q.append(y)
            dist[y]=d+1
        if v==y and dist[x]==INF:
            q.append(x)
            dist[x]=d+1
    for d in dist:
        if d!=0 and d!=INF:
            ans[d] += 1

for a in ans[1:]:
    print(int(a//2))

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(5, 2, 4), [5, 4, 1, 0])

    def test_2(self):
        self.assertEqual(think(3, 1, 3), [3, 0])

    def test_3(self):
        self.assertEqual(think(7, 3, 7), [7, 8, 4, 2, 0, 0])

    def test_4(self):
        self.assertEqual(think(10, 4, 8), [10, 12, 10, 8, 4, 1, 0, 0, 0])


def solve():
    n, x, y = read()
    result = think(n, x, y)
    write(result)


def read():
    return read_int(3)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, x, y):
    MAX_DISTANCE = 10 ** 9
    result = [0] * n
    adjacent_matrix = [[MAX_DISTANCE for _ in range(n)] for _ in range(n)]
    for i in range(n - 1):
        adjacent_matrix[i][i] = 0
        adjacent_matrix[i][i + 1] = 1
        adjacent_matrix[i + 1][i] = 1
    adjacent_matrix[x - 1][y - 1] = 1
    adjacent_matrix[y - 1][x - 1] = 1
    warshall_floyd(adjacent_matrix)
    for i in range(n):
        for j in range(i + 1, n):
            distance = adjacent_matrix[i][j]
            result[distance] += 1
    return result[1:]


def write(result):
    for r in result:
        print(r)


def warshall_floyd(matrix):
    n = len(matrix)

    changed = True
    while changed:
        changed = False
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                for k in range(n):
                    if k == i or k == j:
                        continue
                    old_distance = matrix[i][j]
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
                    if matrix[i][j] < old_distance:
                        changed = True


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
def main():
    input=sys.stdin.readline
    n,x,y=map(int,input().split())
    edge=[]
    for i in range(int(n)):
        tmp=[0 if i==j else 1 if abs(i-j)==1 else -1 for j in range(n)]
        edge.append(tmp)
    edge[x-1][y-1]=1
    edge[y-1][x-1]=1
    step=[0]*n#ある歩数の点の選び方をカウントする
    def bfs(start,graph,step):
        kyori={}#スタートからある点までの距離をある点をキーとして入れる
        num=0
        
        Tovis=[start]
        kyori[start]=0
        visited=[]
        qu=0
        while qu<len(Tovis):
            nex=Tovis[qu]#Tovis.pop(0)
            qu+=1
            visited.append(nex)
            for v in range(len(graph[nex])):
                
                tmp=graph[nex][v]
                if tmp!=-1:
                    if v in visited:
                        continue
                    if v in Tovis:
                        continue
                    Tovis.append(v)
                    res=kyori[nex]+1
                    kyori[v]=res#点ｖまでの距離はその前に通った点までの距離+1
                    step[res]+=0.5#i->j j->iの二回数えてしまうので
    for i in range(n):
        bfs(i,edge,step)
    for i in range(1,len(step)):
        print(int(step[i]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, X, Y = MAP()
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)
 
dic = defaultdict(int)
for i in range(N):
    q = deque()
    q.append(i)
    dist = [INF]*N
    dist[i] = 0
    while q:
        n = q.popleft()
        for node in graph[n]:
            if dist[node] == INF:
                dist[node] = dist[n] + 1
                q.append(node)
 
    for d in dist:
        dic[d] += 1
 
for k in range(1, N):
    print(dic[k]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [10**18] * (n+1)

kyori = [0] * (n+1)
"""
for i in range(n):
    dst[i+1][i+1] = 0
"""
#num = 1

for i in range(1,n):
    #num = 1
    dst[i] = 0
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        """
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        """
        if tmp == x:
            if dst[y] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[x] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[tmp+1] == 10**18:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[tmp-1] == 10**18:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp-1] = tmp_dst+1
        
        #num += 1
        #print(dst[i])
    #exit()
    for j in range(i+1,n+1):
        kyori[dst[j]] += 1
    dst = [10**18] * (n+1)
"""
#print(kyori)
print(dst)
exit()

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1
"""
#print(kyori)
#exit()

for i in range(1,n):
    print(kyori[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections
 
N,X,Y = (int(i) for i in input().split())
 
graph = collections.defaultdict(list)
# X->Yの経路を追加
graph[X].append((1,Y))
graph[Y].append((1,X))
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  graph[i+1].append((1,i))
 
# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}
 
  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      if cost != 0:
        ans[cost - 1] += 1
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections

N,X,Y = (int(i) for i in input().split())

graph = collections.defaultdict(list)
# X->Yの経路を追加
graph[X].append((1,Y))
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  if i >=X and i <= Y:
    graph[i+1].append((1,i))

# 4-3-7 :min
# 5-4-3-7: not min
# 3(X)-4-5(i)-6-7(Y)
# (i-X+1) <= Y-i

# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}

  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      if node_num >= i+1:
        ans[cost-1] += 1
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections
 
N,X,Y = (int(i) for i in input().split())
 
graph = collections.defaultdict(list)
# X->Yの経路を追加
graph[X].append((1,Y))
graph[Y].append((1,X))
# grpah[node_num] = [(cost,next_node_num)]
for i in range(1,N):
  graph[i].append((1,i+1))
  graph[i+1].append((1,i))
 
# ans[i] = 最短経路がiである個数
ans = [0] * (N-1)
# Node 1 ~ N Nodeまでをループ
for i in range(1,N+1):
  # priority_queue : (cost, node_num)
  priority_queue = [(0,i)]
  # 探索したnode
  checked_node = {}
 
  while priority_queue:
    (cost, node_num) = heapq.heappop(priority_queue)
    if node_num in checked_node:
      continue
    else:
      checked_node[node_num] = cost
      for next_cost,next_node_num in graph[node_num]:
        if next_node_num not in checked_node:
          heapq.heappush(priority_queue, (cost + next_cost, next_node_num))
  values = checked_node.values()
  c = collections.Counter(values)
  for k, v in c.items():
      if k != 0:
          ans[k - 1] += v
 
for a in ans:
  print(a//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [10**18] * (n+1)

kyori = [0] * (n+1)
"""
for i in range(n):
    dst[i+1][i+1] = 0
"""
#num = 1

for i in range(1,n):
    #num = 1
    dst[i] = 0
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[y] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[x] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[tmp+1] == 10**18:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[tmp-1] == 10**18:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp-1] = tmp_dst+1
        
        #num += 1
        #print(dst[i])
    #exit()
    for j in range(i+1,n+1):
        kyori[dst[j]] += 1
    dst = [10**18] * (n+1)
"""
#print(kyori)
print(dst)
exit()

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1
"""
#print(kyori)
#exit()

for i in range(1,n):
    print(kyori[i])