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:
from collections import defaultdict,Counter
import queue

N, X, Y = map(int, input().split())
d = defaultdict(list)
d[X].append(Y)
d[Y].append(X)
for i in range(1,N):
    d[i].append(i+1)
    d[i+1].append(i)

ans=defaultdict(int)

for i in range(N):
    dist = [None]*N
    s=i+1
    q=queue.Queue()
    q.put(s)
    dist[i]=0

    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    c=Counter(dist)
    for i,m in c.items():
        ans[i]+=m


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

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

l = np.zeros((n,n),dtype=int)
l = np.array(l)

for i in range(n-1):
    l[i][i+1] = 1
    l[i+1][i] = 1

l[x-1][y-1] = 1
l[y-1][x-1] = 1

a = shortest_path(l)

b = np.triu(a)

c = b.reshape(1,n**2)

d = list(map(int,c[0]))

e = [ i for i in d if i!=0 ]

for i in range(1,n):
    print(e.count(i))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    INF = 10 ** 5
    N, X, Y = map(int, input().split())
    c = [[INF] * N for _ in range(N)]
    for n in range(N-1):
        c[n][n+1] = 1
        c[n+1][n] = 1
    c[X-1][Y-1] = 1
    c[Y-1][X-1] = 1

    ans = [0] * (N-1)
    for s in range(N-1):
        d = dijkstra(s, N, c)
        for i in range(s, N):
            if 0 < d[i] <= N:
                ans[d[i]-1] += 1
    for a in ans:
        print(a)


def dijkstra(s, n, c):
    INF = 10 ** 5
    d = [INF] * n
    u = [False] * n
    d[s] = 0
    while True:
        v = -1
        for i in range(n):
            if (not u[i]) and (v == -1):
                v = i
            elif (not u[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        u[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v] + c[v][j])
    return d

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

distance_list =[]

for i in range(1,n):
    for j in range(i+1,n+1):
        a = j - i
        b = abs(i - x) + abs(j-y) + 1
        if a <= b:
            distance_list.append(a)
        else:
            distance_list.append(b)

count_list = []

for i in range(n-1):
    count_list.append(distance_list.count(i+1))

for i in range(n-1):
    print(count_list[i])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
dis_lis = [0]*N
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i-j)==1:
            dis_lis[1] += 1
        else:
            min1 = abs(i-j)
            min2 = abs(i-X)+abs(j-Y)+1
            min3 = abs(i-Y)+abs(j-X)+1
            dis_lis[min(min1, min2, min3)] += 1
for i in range(1, N):
    print(dis_lis[i])

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans={i:0 for i in range(n)}
dp=[[0]*n for _ in range(n)]
for i in range(1,n+1):
  for j in range(i+1,n+1):
    if j<=x or y<=i:
      dp[i-1][j-1]=j-i  
    elif j<y:
      if i<=x:
        dp[i-1][j-1]=x-i+min(j-x,1+y-j)
      else:
        dp[i-1][j-1]=min(j-i,i-x+y-j+1)
    elif y<=j:
      if i<=x:
        dp[i-1][j-1]=x-i+1+j-y
      else:
        dp[i-1][j-1]=j-y+min(y-i,1+i-x)
    else:
      print("Error")
      print(i,j)
for i in range(0,n):
  for j in range(i,n):
    ans[dp[i][j]]+=1
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
edge = [[] for _ in range(n+1)]
dist = [[-1 for i in range(n+1)] for j in range(n+1)]
counter = [0 for i in range(n)]
for i in range(1, n):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x].append(y)
edge[y].append(x)
# print(edge)

def search(now_edge, i, depth):
    next_list = []
    for next_edge in edge[now_edge]:
        if dist[i][next_edge]==-1:
            dist[i][next_edge] = depth
            dist[next_edge][i] = depth
            next_list.append(next_edge)
    for next_edge in next_list:
        search(next_edge, i, depth+1)

for i in range(1, n+1):
    now_edge = i
    depth = 0
    dist[i][now_edge] = depth
    search_set = set(edge[now_edge])
    while -1 in dist[i][1:]:
        now_search = search_set
        search_set = set()
        depth += 1
        for next_edge in now_search:
            if dist[i][next_edge]==-1:
                dist[i][next_edge] = depth
                dist[next_edge][i] = depth
                search_set = search_set.union(edge[next_edge])
            elif dist[i][next_edge]==depth:
                search_set = search_set.union(edge[next_edge])
    for num in dist[i][1:]:
        counter[num] += 1
# print(dist)

for num in counter[1:]:
    print(num//2)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n, x, y = map(int,input().split()) #n:頂点数　w:辺の数
w = n
ans = [0 for _ in range(n-1)]
# print(ans)
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w-1):
    # x,y = map(int,input().split())
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

# print(dijkstra(0,n,w,cost))
for i in range(n-1):
    aa = dijkstra(i, n, w, cost)
    # print(aa)
    for j in range(i+1, n):
        ans[aa[j]] += 1
ans = ans[1:] + [0]
# print(*ans)
for A in ans:
    print(A)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math
N, X, Y = list(map(int, input().split()))
res = defaultdict(int)
x = []
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i >= j:
            continue
        if i == X and Y == j:
            key = 1
        else:
            key = int(min(j - i, math.fabs(X - i) + math.fabs(Y - j) + 1))
        res[key] += 1


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

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


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

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

ans = [0] * n
for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1

d[x-1][y-1] = 1
d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0

dis = warshall_floyd(d)

for i in range(n):
    for j in range(n):
        if dis[i][j] != float("inf"):
            ans[dis[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Line++
# Use input() to fetch data from STDIN
from collections import defaultdict
d = defaultdict(int)

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

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

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

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

d = defaultdict(int)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        d[g[i][j]] += 1

for k in range(n - 1):
    print(int(d[k + 1] / 2))

Submission status: Time Limit Exceeded

Solution code:
from  collections import defaultdict
N, X, Y = map(int, input().split())
D = defaultdict(int)
for i in range(1,N):
    for j in range(i+1, N+1):
        r = min(j-i, abs(X-i)+abs(X-j)+1, abs(X-i)+abs(Y-j)+1, abs(Y-i)+abs(Y-j)+1)
        D[r] += 1
for i in range(1, N):
    print(D[i])

Submission status: Time Limit Exceeded

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

from itertools import combinations

n,x,y=map(int,readline().split())
dis=[0]*n
lst=list(range(1,n+1))
for a,b in combinations(lst,2):
  if b<=x or a>=y:
    dist=b-a
  else:
    dist=min(b-a, abs(x-a)+abs(y-b)+1,abs(y-a)+abs(x-b)+1)
  dis[dist]+=1
print(*dis[1:],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3

d = []
for i in range(N):
    d.append([2 * 10**3]*N)

for i in range(N - 1):
    d[i][i] = 0
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1
#print(d)

# ワーシャル・フロイドで全点の最短経路を計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

#print(d)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)

for i in range(1, N):
    count = d_list.count(i)
    print(count)

Submission status: Time Limit Exceeded

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

dist_from_X = list(abs(i - (X - 1)) for i in range(N))
dist_from_Y = list(abs(i - (Y - 1)) for i in range(N))

ans_list = [0] * N

for i in range(N):
    for j in range(N):
        i_X_Y_j = dist_from_X[i] + 1 + dist_from_Y[j]
        i_Y_X_j = dist_from_Y[i] + 1 + dist_from_X[j]
        i_j = abs(i - j)
        min_dist_i_j = min(i_X_Y_j, i_Y_X_j, i_j)
        ans_list[min_dist_i_j] += 1

for num in ans_list[1:]:
    print(num // 2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
ans = [0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    if i <= X and j <= X:
      dic = j-i
    elif i >= Y and j >= Y:
      dic = j-i
    elif i <= X and j >= Y:
      dic = (j-i)-(Y-X)+1
    elif X < i < Y and j >= Y:
      dic = min(i-X+1,Y-i)+(j-Y)
    elif i<=X and X < j < Y:
      dic = (X-i)+min(Y-j+1,j-X)
    elif X < i < Y and X < j < Y:
      dic = min(j-i,(i-X+1)+(Y-j))
    ans[dic-1] = ans[dic-1]+1

for ret in ans:
  print(ret)

Submission status: Time Limit Exceeded

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

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0

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

dist[x-1][y-1]=1
dist[y-1][x-1]=1
Washall_Floyd(dist)

counter = Counter(flatten_2dim(dist))
counter = sorted(counter.most_common())[1:]

for key, val in counter:
    print(val//2)
for i in range(n - len(counter)-1):
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


def main():
    N, X, Y = list(map(int, input().split()))
    
    d = [[float("inf")] * N for i in range(N)]
    for i in range(N - 1):
        d[i][i + 1] = 1
        d[i + 1][i] = 1
        d[i][i] = 0
    d[N - 1][N - 1] = 0

    d[X - 1][Y - 1] = 1
    d[Y - 1][X - 1] = 1

    d = warshall_floyd(d, N)
    d = np.array(d)

    for i in range(1, N):
        print((d == i).sum() // 2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def check(p, points, d2):
    if p in points:
        points.remove(p)
        d2.add(p)
    return points, d2


n, x, y = (int(v) for v in input().split())
x -= 1
y -= 1
c = [0] * (n - 1)
for i in range(n):
    points = set(range(n))
    d1 = {i}
    d2 = set()
    points.remove(i)
    for j in range(n - 1):
        for d in d1:
            points, d2 = check(d + 1, points, d2)
            points, d2 = check(d - 1, points, d2)
            if d == x:
                points, d2 = check(y, points, d2)
            if d == y:
                points, d2 = check(x, points, d2)

        c[j] += len(d2)
        d1 = d2
        d2 = set()
for v in c:
    print(str(int(v / 2)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque
n, x, y = list(map(int, input().split()))
G = [[]*n for _ in range(n)]

for i in range(n-1):
    G[i].append((i+1, 1))
    G[i+1].append((i, 1))
G[x-1].append((y-1, 1))
G[y-1].append((x-1, 1))
# print(G)
INF = 10**30
N = n


# s: 開始頂点
# N: 頂点数
# G: グラフ
# G[v][i] = (w, d): 辺v-wのコストは d (0 or 1)
dd = []
for i in range(n):
    s = i
    dist = [10**9] * N
    S = deque([s])
    T = deque()
    dist[s] = 0

    d = 0
    while S:
        while S:
            v = S.popleft()
            for w, c in G[v]:
                if d+c < dist[w]:
                    dist[w] = d+c
                    if c:
                        T.append(w)
                    else:
                        S.append(w)
        S, T = T, S
        d += 1
    dd.append(dist)
for i in range(1, n):
    ans = 0
    for d in dd:
        ans += d.count(i)
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np

N, X, Y = map(int, input().split())
F = [[0 for i in range(N)] for j in range(N)]

for i in range(N - 1):
    F[i][i + 1] = 1
    F[i + 1][i] = 1
F[X - 1][Y - 1] = 1
F[Y - 1][X - 1] = 1

G = csgraph_from_dense(F, null_value=0)
d = dijkstra(G)

# print(F)
# print(d)

# print(np.count_nonzero(d == 1))
for i in range(1, N):
    print(np.count_nonzero(d == i) // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N,X,Y = map(int,input().split(' '))
M = -(-(X+Y)//2)
ANS = []
for i in range(N):
    for j in range(i+1,N):
        d = j-i
        dd = abs(X-1-i)+1+abs(Y-1-j)
        ANS.append(min(d,dd))
ANS.sort()
L = len(ANS)
cnt = 0
ans = [0]*(N-1)
while cnt != L:
    k = ANS[cnt]
    ans[k-1] += 1
    cnt += 1
for i in range(N-1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


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

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)

for k in range(1, n):
    temp = 0
    for i in range(n):
        node = nodes[i]
        q = deque()
        q.append((node, 0))
        done = set()

        while q:
            t = q.popleft()
            node, d = t[0], t[1]
            if d > k:
                break

            if node.idx not in done:
                done.add(node.idx)
                if d == k:
                    temp += 1
                for adj in node.a:
                    q.append((adj, d+1))
    print(temp//2)

Submission status: Time Limit Exceeded

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

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
  
def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

n, x, y = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf] * n for _ in range(n)]
for i in range(n): dist[i][i] = 0

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

dist[x-1][y-1]=1
dist[y-1][x-1]=1
Washall_Floyd(dist)

counter = Counter(flatten_2dim(dist))
counter = sorted(counter.most_common())[1:]

for key, val in counter:
    print(val//2)
for _ in range(n - len(counter)-1):
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    d = [ [ 2 * 10 ** 3 + 1 for j in range(N) ] for i in range(N) ]
    d = np.array(d)

    d[X-1,Y-1] = 1
    d[Y-1,X-1] = 1

    for i in range(N-1):
        d[i,i+1] = 1
        d[i+1,i] = 1
        d[i,i] = 0

    d[N-1,N-1] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i,j] = min(d[i,j],d[i,k]+d[k,j])


    for k in range(1,N):
        res = np.count_nonzero(d == k)
        res //= 2
        print(res)



main()

Submission status: Time Limit Exceeded

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


N, X, Y = map(lambda x: int(x), input().split(" "))
# 距離行列の生成
dist_matrix = [[0] * (N) for _ in range(N)]
for i in range(N-1):
    dist_matrix[i][i+1] = 1
    dist_matrix[i][i+1] = 1

dist_matrix[X-1][Y-1] = 1
dist_matrix[Y-1][X-1] = 1
graph = csr_matrix(dist_matrix)

# ワーシャルフロイド
dist_matrix = floyd_warshall(csgraph=graph, directed=False)

# for i in range(1, N):
#     print(np.count_nonzero(dist_matrix==i)//2)

from collections import Counter, defaultdict
counts = defaultdict(int)
for d in dist_matrix:
    for d2 in d:
        counts[d2] += 1

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

Submission status: Time Limit Exceeded

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

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
aa=[]
ans=defaultdict(int)
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    ac=Counter(a)
    aa.append(ac)

for i in range(len(aa)):
    for a in aa[i].keys():
        ans[a]+=aa[i][a]

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csc_matrix


def warshallFroyd(n):
    graph=[[0]*n for _ in range(n)]

    for i in range(n-1):
        graph[i][i+1]=1
        graph[i+1][i]=1

    graph[x-1][y-1]=1
    graph[y-1][x-1]=1

    graph=csc_matrix(graph)

    return floyd_warshall(graph)


n,x,y=map(int,input().split())
G=warshallFroyd(n)
D=[0]*n
for i in range(n):
    for j in range(i,n):
        D[int(G[i][j])] +=1

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from collections import defaultdict

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


nei_graph = [[0] * N for _ in range(N)]


for a in range(N):
    if a == N - 1:
        break

    nei_graph[a][a + 1] = 1
    nei_graph[a + 1][a] = 1


nei_graph[X - 1][Y - 1] = 1
nei_graph[Y - 1][X - 1] = 1

nei_graph = floyd_warshall(nei_graph)

dic = defaultdict(int)
for i in range(N):
    for j in range(i + 1, N):
        w = nei_graph[i][j]

        dic[w] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y = map(int,input().split())
g = np.zeros((n,n))+float("inf")
for i in range(n-1):
  g[i,i] = 0
  g[i,i+1] = 1
  g[i+1,i] = 1
g[-1,-1] = 0
g[x-1,y-1] = 1
g[y-1,x-1] = 1
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i,j] = min(g[i,j], g[i,k]+g[k,j])
for i in range(1,n):
  print(np.count_nonzero(g==i)//2)

Submission status: Time Limit Exceeded

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

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

edge = [[-1] * N for _ in range(N)]
for i in range(N - 1):
    edge[i][i + 1] = 1
    edge[i + 1][i] = 1
edge[X - 1][Y - 1] = 1
edge[Y - 1][X - 1] = 1

# 隣接行列
G = csgraph_from_dense(edge, null_value=-1)
# 下準備 重みがnull_valueの辺は存在しないとうこと
# 別に隣接行列のままでいい,今回は存在しない辺があるため

d = floyd_warshall(G, directed=True)
# directed初期値True 逆走もできるか

# print(d)

ans = [0] * (N)

for i in range(N):
    for j in range(i, N):
        ans[int(d[i][j])] += 1

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

Submission status: Time Limit Exceeded

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

from itertools import combinations

n,x,y=map(int,readline().split())
dis=[0]*n
lst=list(range(1,n+1))
for a,b in combinations(lst,2):
  dist=min(b-a, abs(x-a)+abs(y-b)+1,abs(y-a)+abs(x-b)+1)
  dis[dist]+=1
print(*dis[1:],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import dijkstra
import numpy as np
N, X, Y = map(int, input().split())
edges = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1
X -= 1
Y -= 1
edges[X][Y] = 1
edges[Y][X] = 1
res = dijkstra(np.array(edges), directed=False)
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        ans[int(res[i][j])] += 1
for k in range(1, N):
    print(ans[k])

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import deque
def resolve():
    N, X, Y = lr()
    edges = [[1]]
    for i in range(1, N-1):
        edges.append([i-1, i+1])
    edges.append([N-2])
    edges[X-1].append(Y-1)
    edges[Y-1].append(X-1)
    cnt = [0]*(N-1)
    for i in range(N):
        s = deque([[i, 1]])
        vis = [0]*N
        vis[i] = 1
        while len(s) > 0:
            v, dis = s.popleft()
            for j in edges[v]:
                if not vis[j]:
                    s.append([j, dis+1])
                    vis[j] = 1
                    cnt[dis-1] += 1
    for c in cnt:
        print(c//2)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


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

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)

for k in range(1, n):
    temp = 0
    for i in range(n):
        node = nodes[i]
        q = deque()
        q.append((node, 0))
        done = set()

        while q:
            t = q.popleft()
            node, d = t[0], t[1]

            if node.idx not in done:
                done.add(node.idx)
                if d == k:
                    temp += 1
                for adj in node.a:
                    q.append((adj, d+1))
    print(temp//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict

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

x -= 1
y -= 1

inf = 1000000000
dist = np.full((n, n), inf, dtype=np.int)

for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        else:
            path1 = abs(j - i)
            path2 = abs(x - i) + 1 + abs(y - j)
            dist[i][j] = min(abs(j - i), path2)

dist_counts = defaultdict(int)
for i in range(n):
    for j in range(i + 1, n):
        d = dist[i][j]
        dist_counts[d] += 1

for k in range(1, n):
    print(dist_counts[k])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
dis_lis = {i:0 for i in range(1, N+1)}
for i in range(N):
    for j in range(N):
        if i==j: continue
        if abs(i-j)==1:
            dis_lis[1] += 1
        else:
            min1 = abs(i-j)
            min2 = abs(i-X)+abs(j-Y)+1
            min3 = abs(i-Y)+abs(j-X)+1
            dis_lis[min(min1, min2, min3)] += 1
for i in range(1, N):
    print(dis_lis[i]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heappop, heappush, heapify

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N, X, Y = MAP()

graph = defaultdict(list)

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

graph[X-1].append((Y-1, 1))
graph[Y-1].append((X-1, 1))

a = dijkstra(graph, 0)
count = defaultdict(int)
for i in range(N):
    a = dijkstra(graph, i)
    
    # print(a[i+1:])
    for c in a[i+1:]:
        count[c] += 1
# print(count)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product,combinations
from collections import defaultdict
inf=10**7
n,x,y=map(int,input().split())
dis={(i,j):inf for i,j in product(range(n),repeat=2)}
for i in range(n-1):
  dis[(i,i+1)]=1
  dis[(i+1,i)]=1
for i in range(n):
  dis[(i,i)]=0
dis[(x-1,y-1)]=1
dis[(y-1,x-1)]=1
for k in range(n):
  for i,j in product(range(n),repeat=2):
    dis[(i,j)]=min(dis[(i,j)],dis[(i,k)]+dis[(k,j)])
cnt=defaultdict(int)
for i,j in combinations(range(n),2):
  cnt[dis[(i,j)]]+=1
for k in range(1,n):
  print(cnt[k])

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
S = [[N]*N for _ in range(N)]

for i in range(N):
    S[i][i] = 0

    if i != N-1:
        S[i][i+1] = 1
        S[i+1][i] = 1

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for _ in range(10):
    for i in range(N):
        for j in range(N):
            for k in range(N):
                S[i][j] = min(S[i][j], S[i][k]+S[k][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import bisect as bs

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

array = [[-1 for i in range(n)] for j in range(n)]

for i in range(n):
  for j in range(n):
    array[i][j] = abs(j-i)
    
for i in range(n):
  if array[i][x] == array[i][y]:
    pass
  
  elif array[i][x] > array[i][y]:
    array[i][x] = array[i][y] + 1
    
    index = x - 1
    while True:
      if index < 0 or array[i][index] <= array[i][index+1]:
        break
        
      array[i][index] = array[i][index+1] + 1
      index -= 1
      
    index = x + 1
    while True:
      if index >= n or array[i][index] <= array[i][index-1]:
        break
        
      array[i][index] = array[i][index-1] + 1
      index += 1
      
  else:
    array[i][y] = array[i][x] + 1
    
    index = y - 1
    while True:
      if index < 0 or array[i][index] <= array[i][index+1]:
        break
        
      array[i][index] = array[i][index+1] + 1
      index -= 1
      
    index = y + 1
    while True:
      if index >= n or array[i][index] <= array[i][index-1]:
        break
        
      array[i][index] = array[i][index-1] + 1
      index += 1
      
ans = [0] * (n+1)
for i in range(n):
  for j in range(i, n):
    tmp = array[i][j]
    ans[tmp] += 1
    
for i in range(1,n):
  print(ans[i])

Submission status: Time Limit Exceeded

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

distance_list =[]


for i in range(1,n):
    for j in range(i+1,n+1):
        a = j - i
        b = abs(i - x) + abs(j-y) + 1
        if a <= b:
            distance_list.append(a)
        else:
            distance_list.append(b)

count_list = []

for i in range(n-1):
    count_list.append(distance_list.count(i+1))

for i in range(n-1):
    print(count_list[i])