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: Runtime Error

Solution code:
import queue

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

G = [[] for _ in range(N + 1)]
for i in range(1, N):
    G[i].append(i + 1)
    G[i + 1].append(i)
G[Y].append(X)
G[X].append(Y)
#print(G)

seen = [False] * (N + 1)
todo = queue.Queue()
route = [0] * (N + 1)
def bfs(parent):
    seen[parent] = True
    #print(route)
    for child in G[parent]:
        if seen[child] == False:
            seen[child] = True
            route[child] = route[parent] + 1
            todo.put(child)
    if not todo.empty():
        bfs(todo.get())

bfs(1)
#print(route)

bucket = [0] * N
for i in range(1, N + 1):
    seen = [False] * (N + 1)
    route = [0] * (N + 1)
    bfs(i)
    for val in route:
        bucket[val] += 1
#print(bucket)
for i in range(1, N):
    print(bucket[i] // 2)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

ma[x-1][y-1] = 1
ma[y-1][x-1] = 1
a = csr_matrix(ma)
b = shortest_path(a)
ans = [0]*(n-1)
for i in range(n):
  l = b[i]
  for num in l:
    if num != 0:
    	ans[int(num)-1] += 1

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

def push(q, tmp, d, D):
    if D[tmp] == -1:
        D[tmp] = d + 1
        q.append(tmp)

ans = [0] * N
for i in range(N):
    D = [-1] * N
    D[s] = 0
    q = deque()
    q.append(s)
    while len(q) > 0:
        tmp = q.popleft()
        d = D[tmp]
        if tmp < N-1:
            push(q, tmp+1, d, D)
        if 0 < tmp:
            push(q, tmp-1, d, D)
        if tmp == X-1:
            push(q, Y-1, d, D)
        if tmp == Y-1:
            push(q, X-1, d, D)

    for j in range(N):
        ans[D[j]] += 1

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

def BFS(s, D):
    D[s] = 0
    q = deque()
    q.put(s)
    while not q.empty():
        tmp = q.appendleft()
        d = D[tmp]
        if tmp < N-1:
            push(q, tmp+1, d, D)
        if 0 < tmp:
            push(q, tmp-1, d, D)
        if tmp == X-1:
            push(q, Y-1, d, D)
        if tmp == Y-1:
            push(q, X-1, d, D)
            
def push(q, tmp, d, D):
    if D[tmp] == -1:
        D[tmp] = d + 1
        q.append(tmp)

ans = [0] * N
for i in range(N):
    D = [-1] * N
    BFS(i, D)
    for j in range(N):
        ans[D[j]] += 1

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

Submission status: Runtime Error

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

#S_Mat = csr_matrix((data, (row, col)), shape=(N,N))
#S_Mat += S_Mat.T

# 最短経路行列の取得
#SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)
SP_Mat = shortest_path(S_Mat)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Runtime Error

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N))
S_Mat += S_Mat.T

# 最短経路行列の取得
#SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)
SP_Mat = shortest_path(S_Mat)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Runtime Error

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N))
S_Mat += S_Mat.T

# 最短経路行列の取得
#SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)
SP_Mat = shortest_path(S_Mat)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Runtime Error

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N))
S_Mat += S_Mat.T

# 最短経路行列の取得
SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Runtime Error

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

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

# スパース行列の作成
data = [1]*N

row = [int(x) for x in range(N-1)]
row.append(X-1)

col = [int(x+1) for x in range(N-1)]
col.append(Y-1)

S_Mat = csr_matrix((data, (row, col)), shape=(N,N))
S_Mat += S_Mat.T

# 最短経路行列の取得
SP_Mat = shortest_path(S_Mat, directed=False, unweighted=True)

for k in range(N-1):
    print(int(np.sum(SP_Mat == k+1)/2))

Submission status: Runtime Error

Solution code:
from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row[i][j]=0
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row[i][j]=1
        else:
            row[i][j] = 2000
    gyoretu.append(row)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if gyoretu[i][j]< gyoretu[i][k] + gyoretu[k][j]:
                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        array+=gyoretu[i][i:]
c=Counter(array)
for i in range(1, N):
    print(c[i])

Submission status: Runtime Error

Solution code:
import networkx as nx
from collections import Counter
import itertools
#import numpy as np

N, X, Y = map(int,input().split())
G = nx.Graph()
Node = range(N)
G.add_nodes_from(Node)
Edge = []
for i in range(N-1):
    Edge.append((i,i+1))
G.add_edges_from(Edge)
G.add_edge(X-1, Y-1)
path = dict(nx.all_pairs_shortest_path_length(G))
length = []

#辞書から値を削除（同じ頂点には行かない）
for i in range(N):
    del path[i][i]
#値だけとりだす
for i in range(N):
    length.append(list(path[i].values()))
#一次元にしてカウント
step = list(itertools.chain.from_iterable(length))
count = Counter(step)
ma = max(step)
for i in range(1,ma+1):
    print(count[i]//2)
for i in range(ma+1, N):
    print(0)

Submission status: Runtime Error

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

res = np.zeros(N - 1, dtype=int)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        r1 = j - i
        r2 = np.abs(X - i) + 1 + np.abs(j - Y)
        dist = min(r1, r2)
        res[dist - 1] += 1
_ = [print(d) for d in res]

Submission status: Runtime Error

Solution code:
n, x, y = map(int,input().split())
dist = [0] * (n-1)
x -= 1
y -= 1
for i in range(n):
  for j in range(i+1, n):
    if (i <= x and j <= x) or (x <= i <= y and x <= j <= y) or (y <= i and y <= j):
      dist[j-i] += 1
    elif i <= x and y <= j:
      dist[j-i-(y-x)+1] += 1
    elif i <= x and x <= j <= y:
      dist[x-i + min(j-x, y-j+1)] += 1
    else:
      dist[j-y + min(y-j, j-x+1)] += 1
for d in dist:
  print(d)

Submission status: Runtime Error

Solution code:
from collections import Counter

#n, x, y = 5, 2, 4
n, x, y = map(int, input().split())
inf = 10**9
#tmp = [[inf]*n]*n の様な配列の初期化では各行のidが同じになってしまう
tmp = [[inf for i in range(n)] for j in range(n-1)]
c = Counter()

def dfs(start, now, cnt):
    global tmp
    if now > n:
        return
    #print(f"{start=},{now=},{cnt=}")
    tmp[start-1][now-1] = min(cnt, tmp[start-1][now-1])
    dfs(start, now+1, cnt+1)
    if now == x:
        dfs(start, y, cnt+1)

for i in range(1, n):
    dfs(i, i, 0)
    #dfs(i, i+1, 1) これは誤り、初期値がxのときにショートカットを見逃す
    c += Counter(tmp[i-1])

ans = sorted(c.items())
for i in range(1, len(ans)-1):
    print(ans[i][1])
print(0)

Submission status: Runtime Error

Solution code:
n,x,y=map(int,input().split())
x-=1
y-=1
ans=[0 for i in range(n)]
for ni in range(n):
    d=[100000 for i in range(n)]
    q=[]
    q.append(ni)
    d[ni]=0
    while q:
        p=q.pop()
        if(p>0 and d[p-1]>d[p]+1):
            q.append(p-1)
            d[p-1]=d[p]+1
        if(p<n-1 and d[p+1]>d[p]+1):
            q.append(p+1)
            d[p+1]=d[p]+1

        if(p==x and d[y]>d[x]+1):
            q.append(y)
            d[y]=d[x]+1
        if(p==y and d[x]>d[y]+1):
            q.append(x)
            d[x]=d[y]+1
        break

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

Submission status: Runtime Error

Solution code:
def abs(x):
    if x < 0:
        return x;
    else:
        return -x;

n, x, y = (int(i) for i in input().split());

x -= 1;
y -= 1;

cnt = [0 for k in range(n - 1)];

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

for i in cnt:
    print(i);

Submission status: Runtime Error

Solution code:
N,X,Y = map(int,input().split())
D = [k-1 if k<Y else k-1-(Y-X)+1 for k in range(2,N+1)]#distance of 1tok
lstK = [0]*(N-1)#index:0toN-1

for i in range(2,N-1):
    for j in range(i+1,N):
        lstK[D[j]-D[i]-1] += 1
for p in D:
    lstK[p-1] += 1
for _ in range (N-1)
    print(lstK[_])

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
@nJit
def D_160():
    N, X, Y = map(int, input().split())
    count_list = [[0]*N for i in range(N)]
    for i in range(0,N):
        for j in range(i,N):
            count_list[i][j] = min(j-i,abs(X-1-i) + abs(j-(Y-1)) + 1)
    
    #print(count_list)
    count_list = sum(count_list,[])
    
    for i in range(1,N):
        print(count_list.count(i))

D_160()

Submission status: Runtime Error

Solution code:
from numba import njit
@nJit
def D_160():
    N, X, Y = map(int, input().split())
    count_list = [[0]*N for i in range(N)]
    for i in range(0,N):
        for j in range(i,N):
            count_list[i][j] = min(j-i,abs(X-1-i) + abs(j-(Y-1)) + 1)
    
    #print(count_list)
    count_list = sum(count_list,[])
    
    for i in range(1,N):
        print(count_list.count(i))

D_160()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#借り物 テスト
ans=[0]*n #個数を数えるのにバケットを用意する
for i in range(1,n+1): 
    for j in range(i+1,n+1):
        dist1=j-i
        dist2=abs(x-i)+abs(y-j)+1
        #dist3=abs(y-i)+abs(x-j)+1
        d=min(dist1,dist2) 
        ans[d]+=1 
for i in range(1,n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
dist_list = []*N

for i in range(N):
    for j in range(i+1, N):
        a = j - i
        b = abs(i+1 - X) + abs(j+1 -Y) + 1
        dist_list[min(a,b)] += 1
        
for k in range(N-1):
    print(dist_list.count(k+1))

Submission status: Runtime Error

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
        distance_list.append(min(a,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: Runtime Error

Solution code:
n,a,b = map(int,input().split())
count_list = [0]*n

cnt = 0
for i in range(1,n):
  for k in range(i+1,n+1):
    a0 = k-i
    a1 = abs(a-i)+ abs(b-k) + 1
    count_list[cnt] = min(a0,a1)
    #print(i,"@",k,"@",a0,"@",a1,"@",count_list,cnt)
    cnt += 1
    
    

for result in range(1,n+1):
  print(count_list.count(result))

Submission status: Runtime Error

Solution code:
n,a,b = map(int,input().split())
count_list = [0]*n

cnt = 0
for i in range(1,n):
  for k in range(i+1,n+1):
    a0 = k-i
    a1 = abs(a-i)+ abs(b-k) + 1
    count_list[cnt] = min(a0,a1)
    cnt += 1
    
    

for result in range(1,n):
  print(count_list.count(result))

Submission status: Runtime Error

Solution code:
n,a,b = map(int,input().split())
count_list = [0]*n

cnt = 0
for i in range(1,n):
  for k in range(i+1,n+1):
    a0 = k-i
    a1 = abs(a-i)+ abs(b-k) + 1
    count_list[cnt] = min(a0,a1)
    #print(i,"@",k,"@",a0,"@",a1,"@",count_list,cnt)
    cnt += 1
    
    

for result in range(1,n):
  print(count_list.count(result))

Submission status: Runtime Error

Solution code:
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number
for i in range(num_data[0]):
    for l in range(num_data[0] - 1):
        result = min(abs(i - l),abs(i - num_data[1] - 1) + 1 + abs(l - num_data[2] - 1),abs(i - num_data[2] - 1) + 1 + abs(l - num_data[1] - 1))
        cost[num_data[0] - result] += 1
print(cost)

Submission status: Runtime Error

Solution code:
n, x, y = map(inty, input().split())
X = min(x,y)
Y = max(x,y)
x =X
y = Y
sum = x +y +1
dist = x+1
for i in range(2,dist):
	sum += dist//i
dist = n+1-y
for j in range(2,dist):
	sum += dist//j
dist = y+1-x
sum+= dist
for k in range(2,dist):
  sum += dist//k
sum+= y-n+2

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1　　#１のところを０にするなど一つずつずらす
 
def dist(a, b):
  return min(abs(b-a), abs(X-a) + 1 + abs(b-Y), abs(Y-a) + 1 + abs(b-X))
 #＋１は間の一つ繋がっている分

ANS = [0] * N  　　　#0がN個のリストを作成。一つ目はk=0の時（同じところ）
for i in range(N):
  for j in range(i):
    ANS[dist(i, j)] += 1　　#0にずらしたことで０から始まるi,jに対応できている
        
        #i,jの最小値のindexに１ずつ足していく
        
for a in ANS[1:]:　#indexが１以降（数字の差が１以上）のものを一つづつ出力
  print(a)

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1　　#１のところを０にするなど一つずつずらす
 
def dist(a, b):
    return min(abs(b-a), abs(X-a) + 1 + abs(b-Y), abs(Y-a) + 1 + abs(b-X))
 #＋１は間の一つ繋がっている分
 
ANS = [0] * N  　　　#0がN個のリストを作成。一つ目はk=0の時（同じところ）
for i in range(N):
    for j in range(i):
        ANS[dist(i, j)] += 1　　#0にずらしたことで０から始まるi,jに対応できている
        
        #i,jの最小値のindexに１ずつ足していく
        
for a in ANS[1:]:　#indexが１以降（数字の差が１以上）のものを一つづつ出力
  print(a)

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1　　#１のところを０にするなど一つずつずらす
 
def dist(a, b):
    return min(abs(b-a), abs(X-a) + 1 + abs(b-Y), abs(Y-a) + 1 + abs(b-X))
 #＋１は間の一つ繋がっている分

ANS = [0] * N  　　　#0がN個のリストを作成。一つ目はk=0の時（同じところ）
for i in range(N):
    for j in range(i):
        ANS[dist(i, j)] += 1　　#0にずらしたことで０から始まるi,jに対応できている
        
        #i,jの最小値のindexに１ずつ足していく
 
for a in ANS[1:]:　#indexが１以降（数字の差が１以上）のものを一つづつ出力
    print(a)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.graph = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, undirected=True):
        self.graph[start].append(end)
        if undirected:
            self.graph[end].append(start)

    # depth = distance
    def search(self, start_node):
        order = [-1] * self.n # a bfs ordering of each vertex
        parent = [-1] * self.n # parent of each vertex in the bfs search tree
        depth = [-1] * self.n # the depth of each vertex
        q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
        num = 0 # current ordering
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0: # visited v for the first time
                order[v] = num; parent[v] = p; depth[v] = d
                num += 1
                for u in adj_list[v]:
                    if order[u] >= 0: continue
                    q.append((u, v, d+1))
        return order, parent, depth



# BFS
def breadth_first_search(adj_list, start_node):
    N = len(adj_list)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while len(q) > 0:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; parent[v] = p; depth[v] = d
            num += 1
            for u in self.graph[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth


# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    bfs = BreadthFirstSearch(N)
    for val in _data:
        bfs.add_edge(val[0]-1, val[1]-1)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, depth = bfs.search(i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.graph = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, undirected=True):
        self.graph[start].append(end)
        if undirected:
            self.graph[end].append(start)

    # depth = distance
    def search(self, start_node):
        order = [-1] * self.n # a bfs ordering of each vertex
        parent = [-1] * self.n # parent of each vertex in the bfs search tree
        depth = [-1] * self.n # the depth of each vertex
        q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
        num = 0 # current ordering
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0: # visited v for the first time
                order[v] = num; parent[v] = p; depth[v] = d
                num += 1
                for u in adj_list[v]:
                    if order[u] >= 0: continue
                    q.append((u, v, d+1))
        return order, parent, depth



# BFS
def breadth_first_search(adj_list, start_node):
    N = len(adj_list)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while len(q) > 0:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; parent[v] = p; depth[v] = d
            num += 1
            for u in adj_list[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth


# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    bfs = BreadthFirstSearch(N)
    for val in _data:
        bfs.add_edge(val[0]-1, val[1]-1)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, depth = bfs.search(i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque


class BreadthFirstSearch:
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.graph = [[] for _ in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, undirected=True):
        self.graph[start].append(end)
        if undirected:
            self.graph[end].append(start)

    # depth = distance
    def search(self, start_node):
        order = [-1] * self.n # a bfs ordering of each vertex
        parent = [-1] * self.n # parent of each vertex in the bfs search tree
        depth = [-1] * self.n # the depth of each vertex
        q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
        num = 0 # current ordering
        while len(q) > 0:
            v, p, d = q.popleft()
            if order[v] < 0: # visited v for the first time
                order[v] = num; parent[v] = p; depth[v] = d
                num += 1
                for u in adj_list[v]:
                    if order[u] >= 0: continue
                    q.append((u, v, d+1))
        return order, parent, depth



# BFS
def breadth_first_search(adj_list, start_node):
    N = len(adj_list)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(start_node, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while len(q) > 0:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num; parent[v] = p; depth[v] = d
            num += 1
            for u in adj_list[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth


# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    bfs = BreadthFirstSearch(N)
    for val in _data:
        bfs.add_edge(val[0], val[1])
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, depth = bfs.search(i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Runtime Error

Solution code:
from collections import deque
N,X,Y=map(int,input().split())

count=[0]*N

def bfs(start):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=deque()
    q.append([start,0])
    dist[start]=0
    while not q.empty():
        j,kyori=q.popleft()

        if j-1>=1:
            if dist[j-1]==-1:
                q.append([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.append([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.append([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.append([X,kyori+1])
            dist[X]=kyori+1

    return dist[1:]

def main():
    for start in range(1,N+1):
        dist=bfs(start)
        for d in dist:
            count[d]+=1

    for i in count[1:]:
        print(i//2)

main()

Submission status: Runtime Error

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

ans = [0] * (N-1)
for i in range(1,N+1):
	for j in range(i, N+1):
		k = min(j-i, abs(X-i) + abs(Y-j) + 1)
		ans[k-1] += 1

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

Submission status: Runtime Error

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

and = [0] * (N-1)
for i in range(1,N+1):
	for j in range(i, N+1):
		k = min(j-i, abs(X-i) + abs(Y-j) + 1)
		ans[k-1] += 1

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

Submission status: Runtime Error

Solution code:
# from sys import stdin

# # 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


# if __name__ == '__main__':
#     data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
#     get_result(data)

from sys import stdin
from collections import deque


# 重みなしグラフの隣接リスト
# 0-indexed nodes
def get_adj_list(num_nodes, data, undirected=True):
    graph = [[] for _ in range(num_nodes)]
    for val in data:
        x, y = val
        graph[x-1] = graph[x-1] + [y-1]
        if undirected:
            graph[y-1] = graph[y-1] + [x-1]
    return graph


# BFS
def depth_first_search(adj_list, start_node)):
    N = len(adj_list)
    preorder = [-1] * N # a dfs preordering of each vertex
    postorder = [-1] * N # a dfs postordering of each vertex
    parent = [-1] * N # parent of each vertex in the dfs search tree
    depth = [-1] * N # the depth of each vertex
    stack = [(start_node, -1, 0)] # (vertex, parent, status)
    pre_num = 0 # current preordering
    post_num = 0 # current postordering
    d = 0 # current depth
    while len(stack) > 0:
        v, p, st = stack.pop()
        if st == 0 and preorder[v] < 0: # visited v for the first time
            preorder[v] = pre_num; parent[v] = p; depth[v] = d
            pre_num += 1
            n_children = 0
            for u in adj_list[v]:
                if preorder[u] >= 0: continue
                if n_children == 0:
                    stack += [(v, p, 2), (u, v, 0)]
                    n_children += 1
                else:
                    stack += [(v, p, 1), (u, v, 0)]
                    n_children += 1
            if n_children == 0: # v is a leaf
                postorder[v] = post_num
                post_num += 1
                d -= 1
            else:
                d += 1
        elif st == 0 and preorder[v] >= 0: # the edge (v, p) is a back edge
            d -= 1
        elif st == 1: # now searching
            d += 1
        else: # search finished (st=2)
            postorder[v] = post_num
            post_num += 1
            d -= 1
    return preorder, postorder, parent, depth


# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, _,  depth = depth_first_search(adj_list, i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque


# 重みなしグラフの隣接リスト
# 0-indexed nodes
def get_adj_list(num_nodes, data, undirected=True):
    graph = [[] for _ in range(num_nodes)]
    for val in data:
        x, y = val
        graph[x-1] = graph[x-1] + [y-1]
        if undirected:
            graph[y-1] = graph[y-1] + [x-1]
    return graph


# BFS
def breadth_first_search(adj_list, start_node):
    N = len(adj_list)
    order = [-1] * N # a bfs ordering of each vertex
    parent = [-1] * N # parent of each vertex in the bfs search tree
    depth = [-1] * N # the depth of each vertex
    q = deque([(s, -1, 0)]) # (vertex, parent, depth)
    num = 0 # current ordering
    while q:
        v, p, d = q.popleft()
        if order[v] < 0: # visited v for the first time
            order[v] = num
            parent[v] = p
            depth[v] = d
            num += 1
            for u in adj_list[v]:
                if order[u] >= 0: continue
                q.append((u, v, d+1))
    return order, parent, depth

# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        _, _, depth = breadth_first_search(adj_list, i)
        for j in range(i, N):
            dist_cnt[depth[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Runtime Error

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

edges = defaultdict(lambda: [])
for i in range(1, n):
    edges[i].append(i+1)
    edges[i+1].append(i)
edges[x].append(y)
edges[y].append(x)

# 幅優先
counter = [0 for i in range(n)]
for i in range(1, n+1):
    d = deque()
    dist = [-1 for _ in range(n+1)]
    d.append((i, -1))
    while len(d) > 0:
        e, pre_dist = d.popleft()
        if dist[e] != -1:
            continue
        else:
            dist[e] = pre_dist + 1
            for next_e in edges[e]:
                if not is_checked[next_e]:
                    d.append((next_e, pre_dist+1))
    for j in range(i+1, n+1):
        counter[dist[j]-1] += 1
print("\n".join(list(map(str, counter[1:]))))

Submission status: Runtime Error

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

for i in d:
  print(i)

Submission status: Runtime Error

Solution code:
n,x,y = map(int,input().split())
g = [[]for i in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(1,n-1):
  g[i].append(i-1)
  g[i].append(i+1)
ans = [0]*(n-1)
def dfs(b,c):
  for i in g[b]:
    if a[i] > c+1:
      a[i] = c+1
      dfs(i,c+1)
    
for i in range(n):
  a = [999999999]*n
  a[i] = 0
  dfs(i,0)
  for j in a:
    if j == 0:
      continue
    ans[j-1] += 1
for i in ans:
  print(i//2)