Problem:


Score : 500 points

Problem Statement

Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are described by a grid of characters S.
If S_{i,j} is 1, there is an edge connecting Vertex i and j; otherwise, there is no such edge.

Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k, in such a division.

Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j), there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.

Constraints

2 \leq N \leq 200

S_{i,j} is 0 or 1.

S_{i,i} is 0.

S_{i,j}=S_{j,i}

The given graph is connected.

N is an integer.

Input

Input is given from Standard Input in the following format:

N
S_{1,1}...S_{1,N}
:
S_{N,1}...S_{N,N}

Output

If it is impossible to divide the vertices into sets so that the condition is satisfied, print -1.
Otherwise, print the maximum possible number of sets, k, in a division that satisfies the condition.

Sample Input 1

2
01
10

Sample Output 1

2

We can put Vertex 1 in V_1 and Vertex 2 in V_2.

Sample Input 2

3
011
101
110

Sample Output 2

-1

Sample Input 3

6
010110
101001
010100
101000
100000
010000

Sample Output 3

4



Sample input:
2
01
10


Sample output:
2

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        weight[x] += weight[par[x]]
        par[x] = r
        return r

def union(x,y,w):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        par[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        par[ry] = rx
        weight[ry] = - w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1
def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight[x] - weight[y]

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 = I()
S = [input() for _ in range(n)]
dist = [[inf]*n for _ in range(n)]
par = [i for i in range(n)]
weight = [0]*n
rank = [0]*n
for i in range(n):
    s = S[i]
    for j in range(i+1,n):
        if s[j] == '1':
            dist[i][j] = 1
            dist[j][i] = 1
            if not same(i,j):
                union(i,j,1)
            else:
                if diff(i,j) == 0:
                    print(-1)
                    quit()

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
lst = []
ans = 0
for i in range(n):
    lst.append(max(d[i]))
M = max(lst)
print(M+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
dis=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	x=input()
	for j in range(n):
		if x[j]=="1":
			dis[i][j]=int(x[j])
		else:
			dis[i][j]=10**9
d=[10**10]*n
d[0]=0
s=set()
for i in range(n):
	q=10**11
	for j in range(n):
		if (j not in s) and q>d[j]:
			q=d[j]
			lit=j
	s.add(lit)
	for j in range(n):
		if j not in s:
			if d[j]>d[lit]+dis[lit][j]:
				d[j]=d[lit]+dis[lit][j]
d.sort()
ans=n
if n==3:
	print(-1)
	exit()
for i in range(len(d)-1):
	if d[i]==d[i+1]:
		ans-=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = [[int(c) for c in l.strip()] for l in sys.stdin]
dp = [ [False]*(i+1) for i in range(n) ]
count = -1
if s[0][1] == 1:
  dp[1][0], dp[1][1] = True, True
  count = 2
for i in range(2, n):
  for j in range(i):
    if dp[i-1][j] and s[i][j] == 1:
      dp[i][i] = True
      if count < i+1:
        count = i+1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans, e = N, 0
for _ in range(N):
    s = input()
    d = s.count('1')
    e += d
    if d > 2:
        ans -= d - 2

e /= 2 
if ans > 0:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
m = []
import collections
for i in range(n):
    m.append(input())
line = []
for i in range(n + 1):
    line.append(collections.deque([]))

for i in range(n):
    for j in range(i,n):
        if m[j][i] == "1":
            line[i+1].append(j+1)

# 各点が所属する位置
group = [300] * (n+1)
group_min = 300
group_max = 300
group[1] = 300

can = True
for i in range(1, n + 1):
    #print("見るのは{0}です".format(i))
    lineto = []
    for j in range(i, 0, -1):
        #print("seek:{0}".format(j))
        usecount = 0
        for k in range( len(line[j]) ):
            #print("k = {0}, data = {1}".format(k, line[j]))
            if i < line[j][k]:
                #print(" no see [{0}] = {1}".format(k, line[j][k]))
                break
            usecount += 1
            item = line[j][k]
            #print("★pop = {0}".format(item))
            lineto.append(j)
        for k in range(usecount):
            item = line[j].popleft()
    #print("行くべきは{0}".format(lineto))
    groupto = list(map(lambda x: group[x], lineto))
    if len(groupto) == 0:
        #print("つながる先はないのでスキップ")
        continue
    #print("つながるべきグループは{0}".format(groupto))
    if (max(groupto) - min(groupto)) > 2:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 1:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 2:
        target = (max(groupto) + min(groupto)) // 2
        #print("間に存在しないといけません。 {1} = {0}".format(target, i))
        group[i] = target
    else:
        # なるべく差が開いている方がに送る
        if (max(groupto) + 1) > group_max:
            target = max(groupto) + 1
            #print("maxを更新できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        elif (min(groupto) + 1) > group_min:
            target = min(groupto) - 1
            #print("minを後進できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1
        elif abs(max(groupto)) >= abs(min(groupto)):
            target = max(groupto) + 1
            #print("正のほうがおおきいか一緒なのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        else:
            target = min(groupto) - 1
            #print("負のほうが遠いのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1

group = group[1:]
if None in group:
    print(-1)
elif can:
    print(1 + max(group) - min(group))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd) != 1: flag = False
        elif dist[nn] != nd:
            flag = False
            break
    #print(i, dist)
    return (ans if flag else 0)

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = -1
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    colq = collections.deque()
    colq.append((0, 0))
    while colq:
        now_node, now_col = colq.popleft()
        if col[now_node] == -1:
            col[now_node] = now_col
            for next_node in edge[now_col]: colq.append((next_node, 1 ^ now_col))
        else:
            if col[now_node] != now_col: 
                print(-1)
                break
    else:
        ans = 1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
check = []
testc = 1000
for i in range(n):
    test = 0
    for c in s[i]:
        test += int(c)
    if test == testc:
        check.append(i)
    elif test < testc:
        check.clear()
        testc = test
        check.append(i)

res = -1
for i in check:
    tres = 1
    flag = [-2 for _ in range(n)]

    flag[i] = 1
    que = [i]
    while que:
        target = que.pop()
        for j in range(n):
            if s[target][j] == "1":
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    tres = -1
                    break
        if tres == -1:
            break
    if tres == -1:
        continue
    else:
        res = max(res, max(flag))

print(res)

Submission status: Wrong Answer

Solution code:

N = int(input())
S = [input() for _ in range(N)]

import sys
import queue

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N//10 + 1):
    q = queue.Queue()
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.put(kk)
    VC = 1
    while VC < N:
        nextv = []
        while not(q.empty()):
            nextv.append(q.get())
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            if not(visited[nextv[i]]):
                visited[nextv[i]] = True
                VC += 1
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    q.put(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        
#
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        weight[x] += weight[par[x]]
        par[x] = r
        return r

def union(x,y,w):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        par[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        par[ry] = rx
        weight[ry] = - w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1
def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight[x] - weight[y]

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 = I()
S = [input() for _ in range(n)]
dist = [[inf]*n for _ in range(n)]
par = [i for i in range(n)]
weight = [0]*n
rank = [0]*n
for i in range(n):
    s = S[i]
    for j in range(i+1,n):
        if s[j] == '1':
            dist[i][j] = 1
            dist[j][i] = 1
            if not same(i,j):
                union(i,j,1)
            else:
                if diff(i,j) == 0:
                    print(-1)
                    quit()

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
lst = []
ans = 0
for i in range(n):
    lst.append(max(d[i]))
M = max(lst)
c = lst.count(M)
if c == M+1:
    print(M+1)
else:
    print(M)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
for i in range(N):
    S.append(list(input()))

flag = 0

memo1 = [50000]*N
nows = set([0])
t = -1
visited = set([])

while True:
    t += 1
    next = set([])
    for now in nows:
        if t < memo1[now]:
            memo1[now]=t
            visited.add(now)
        temp = []
        for j in range(N):
            if (S[now][j]=='1')and(j not in visited):
                temp.append(j)
        next |= set(temp)
    nows = next
    if len(nows)==0:
        break

far1 = memo1.index(max(memo1))

for i in range(N):
    for j in range(N):
        if (memo1[i]==memo1[j])and(S[i][j]=='1'):
            flag = 1
        if flag == 1:
            break
    if flag == 1:
        break

memo2 = [50000]*N
nows = set([far1])
t = -1
visited = set([])

while True:
    t += 1
    next = set([])
    for now in nows:
        if t < memo2[now]:
            memo2[now]=t
            visited.add(now)
        temp = []
        for j in range(N):
            if (S[now][j]=='1')and(j not in visited):
                temp.append(j)
        next |= set(temp)
    nows = next
    if len(nows)==0:
        break
far2 = memo2.index(max(memo2))
output = max(memo2)

for i in range(N):
    for j in range(N):
        if (memo2[i]==memo2[j])and(S[i][j]=='1'):
            flag = 1
        if flag == 1:
            break
    if flag == 1:
        break

if flag == 0:
    print(output+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(input())

INF = float('inf')
def get_farest_bf(s):
    D = [INF] * N
    D[s] = 0
    for i in range(N):
        i = (i+s) % N
        for j in range(N):
            if V[i][j] == '1':
                if D[j] > D[i] + 1:
                    D[j] = D[i] + 1

    invalid = False
    for i in range(N):
        for j in range(i+1, N):
            if D[i] == D[j] and V[i][j] == '1':
                invalid = True
                break
        if invalid:
            break
    if invalid:
        return -1, None
    distmax = max(D)
    t = D.index(distmax)
    return distmax, t

dist, f = get_farest_bf(0)
if dist < 0:
    print(-1)
else:
    
    diameter, _ = get_farest_bf(f)
    print(diameter+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque

import sys
import math
from collections import defaultdict, deque
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        pass

    def add_edge(self, from_, to_):
        """必ず0インデックスで入力すること。
        """
        self.E[from_].append((to_, 1))
        pass


def solve(N: int, S: "List[str]"):

    g = Graph(N)
    for i, s in enumerate(S):
        for j, c in enumerate(s):
            if c == "1":
                g.add_edge(i, j)

    visited = [False]*N
    q = deque()
    q.append(0)
    while len(q) > 0:
        node = q.popleft()
        if visited[node] == True:
            continue
        visited[node] = True
        for i, w in g.E[node]:
            if visited[i] is False:
                q.append(i)

    depth = [-2]*N
    q.append((node, 1))
    while len(q) > 0:
        node, d = q.popleft()
        if depth[node] != -2:
            continue
        depth[node] = d
        for i, w in g.E[node]:
            if depth[i] == -2:
                q.append((i, d+1))
            elif d == depth[i]:
                print(-1)
                return
    print(d)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

N = int(input())
S = [input() for _ in range(N)]

import sys
import queue

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N//2):
    q = queue.Queue()
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.put(kk)
    VC = 1
    while VC < N:
        nextv = []
        while not(q.empty()):
            nextv.append(q.get())
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            if not(visited[nextv[i]]):
                visited[nextv[i]] = True
                VC += 1
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    q.put(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        
#
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd) != 1: flag = False
        elif dist[nn] != nd:
            ans = -1
            break
    #print(i, dist)
    return (ans if flag else -1)

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = -1
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    colq = collections.deque()
    colq.append((0, 0))
    while colq:
        now_node, now_col = colq.popleft()
        if col[now_node] == -1:
            col[now_node] = now_col
            for next_node in edge[now_col]: colq.append((next_node, 1 ^ now_col))
        else:
            if col[now_node] != now_col: 
                print(-1)
                break
    else:
        ans = -1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import combinations

N = int(input())
S = [input() for _ in range(N)]
dist = [-1] * N
q = deque([(0, 0)])
max_d = 0
while q:
    v, d = q.popleft()
    if dist[v] != -1: continue
    dist[v] = d
    max_d = max(max_d, d)
    for u, s in enumerate(S[v]):
        if s == '1' and dist[u] == -1:
            q.append((u, d+1))
x = dist.index(max_d)

diameter = 0
dist = [-1] * N
q = deque([(x, -1, 0)])
while q:
    v, p, d = q.popleft()
    if dist[v] != -1: continue
    dist[v] = d
    diameter = max(diameter, d)
    for u, s in enumerate(S[v]):
        if u == p: continue
        elif s == '1' and dist[u] == -1:
            q.append((u, v, d+1))

infeasible = False
partition = {i: [] for i in range(diameter+1)}
for v, d in enumerate(dist):
    partition[d].append(v)
for i in range(1, diameter+1):
    for u, v in combinations(partition[i], 2):
        if S[u][v] == '1': infeasible = True; break
print(diameter + 1 if not infeasible else -1)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[[None,i] for i in range(N)]
g=[]
for i in range(N):
    S=input()
    r=[]
    for j in range(N):
        if S[j]=="1":
            r.append(j)
    g.append(r)
l[0][0]=0
a=-2
for _ in range(N-1):
    for i in range(1,N):
        for j in g[i]:
            if j!=0:
                l[i][1]=min(l[i][1],l[j][1])
            if l[i][0]==None:
                if l[j][0]==1:
                    l[i][0]=0
                elif l[j][0]==0:
                    l[i][0]=1
            else:
                if l[i][0]==l[j][0]:
                    a=-1
for _ in range(500):
    for i in range(1,N):
        for j in g[i]:
            if l[j][0]!=l[i][0]+1:
                break
        else:
            l[i][0]+=2
if a==-1:
    print(-1)
else:
    l.sort(reverse=1)
    a=l[0][0]+1
    for i in range(1,N):
        if l[i][1]!=l[0][1]:
            a+=l[i][0]
            break
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
  
n = int(input())
g = []
for i in range(n):
  g.append(input())
  g[i] = list(g[i])

tmp = [[] for n in range(n)]
#print(tmp)
for i,a in enumerate(g):
  for j,b in enumerate(a):
    #print(b,i,j)
    if b == '1' and i<j:
      tmp[i].append(j)
#print(tmp)
for a in tmp:
  for j in a:
    #print(a,tmp[j])
    if not set(a) & set(tmp[j]):
      continue
    else:
      print(-1)
      sys.exit()
ans = 0
for i in tmp:
  if not i:
    ans+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, = map(int, sys.stdin.readline().rstrip().split(" "))
matrix = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
map = []
for i in range(N):
    map_row = []
    for j in range(N):
        if matrix[i][j] == 1:
            map_row.append(j)
    map.append(map_row)
path_visited = [[False for _ in range(N)]for __ in range(N)]
# print(map)

# leaves = set()
# for i in range(N):
#     if len(map[i]) == 1:
#         leaves.add(i)
# # print("leaves:", leaves)
# leaves_distances = []
root = 0
distances = {root:0}
# visited = {root}
visiting = [root]
distance = 1
for _ in range(N):
    visiting_next = []
    # print("distance", distance)
    for n in visiting:
        # print(n)
        # print(map[n])
        for target in map[n]:
            # print("target:", target)
            if not target in distances:
                visiting_next.append(target)
                distances[target] = distance
            else:
                # print(distances, n, "->", target, distance)
                if distances[target] < distance and not path_visited[n][target]:
                    print(-1)
                    exit(0)
            path_visited[n][target] = True
            path_visited[target][n] = True

                # visited.add(target)
                # if target in distances:
                #     leaves_distances.append(distance)
    visiting = visiting_next
    distance+=1
# print(leaves_distances)
distance_set = list(sorted(set(distances.values())))
print(distance_set[-1]+distance_set[-2]+1)

exit(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from scipy.sparse.csgraph import shortest_path

N = int(input())
graph_list = []
for i in range(N):
    S = str(input())
    graph_list.append(list(map(int, list(S))))
graph_array = np.array(graph_list)
impossible_flag = 0
for i in range(N):
    for j in range(i, N):
        if graph_array[i][j] == 1:
            for k in range(j, N):
                if graph_array[j][k] == 1 and graph_array[k][i] == 1:
                    impossible_flag = 1
                    break
            else:
                continue
            break
    else:
        continue
    break

if impossible_flag == 1:
    print(-1)
else:
    shortest_path_array = shortest_path(graph_array)
    ans = 0
    for i in range(len(shortest_path_array)):
        for j in range(len(shortest_path_array[i])):
            if shortest_path_array[i][j] > ans:
                ans = int(shortest_path_array[i][j])
    ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())

res = -1
for i in range(0, n):
    tres = 1
    flag = [-2 for j in range(n)]
    flag[i] = 1
    que = [i]
    while que:
        target = que.pop()
        for j in range(n):
            if s[target][j] == "1":
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    tres = -1
                    break
        if tres == -1:
            break
    if tres == -1:
        continue
    else:
        res = max(res, max(flag))

print(res)

Submission status: Wrong Answer

Solution code:
import sys, collections

def longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd > 1): flag = False
        elif dist[nn] != nd:
            ans = -1
            break
    #print(i, dist)
    return (ans if flag else -1)

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = -1
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    colq = collections.deque()
    colq.append((0, 0))
    while colq:
        now_node, now_col = colq.popleft()
        if col[now_node] == -1:
            col[now_node] = now_col
            for next_node in edge[now_col]: colq.append((next_node, 1 ^ now_col))
        else:
            if col[now_node] != now_col: 
                print(-1)
                break
    else:
        ans = -1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def GraphPartition(N, Mtx):
	rslt = 0
	for i in range(N):
		for j in range(i+1, N):
			connect = 0
			if Mtx[i][j] == 0:
				continue
			if i < N-1 and j < N-1:
				connect = Mtx[i+1][j+1] + Mtx[i][j+1]
			if connect == 2:
				rslt = -1
				break
			parent = 0
			if i > 0:
				parent = Mtx[i-1][j-1] + Mtx[i-1][j]
			if parent == 0:
				rslt += 1
		if rslt == -1:
			break
	if rslt == -1:
		print(-1)
	else:
		print(rslt * 2)

N = int(input())
Mtx = []
for i in range(N):
	tmp = [int(x) for x in str(input())]
	Mtx.append(tmp)
GraphPartition(N, Mtx)

Submission status: Wrong Answer

Solution code:
n = int(input())
m = []
import collections
for i in range(n):
    m.append(input())
line = []
for i in range(n + 1):
    line.append(collections.deque([]))

for i in range(n):
    for j in range(i,n):
        if m[j][i] == "1":
            line[i+1].append(j+1)

# 各点が所属する位置
group = [None] * (n+1)
group_min = 0
group_max = 0
group[1] = 0

can = True
for i in range(1, n + 1):
    #print("見るのは{0}です".format(i))
    lineto = []
    for j in range(i, 0, -1):
        #print("seek:{0}".format(j))
        usecount = 0
        for k in range( len(line[j]) ):
            #print("k = {0}, data = {1}".format(k, line[j]))
            if i < line[j][k]:
                #print(" no see [{0}] = {1}".format(k, line[j][k]))
                break
            usecount += 1
            item = line[j][k]
            #print("★pop = {0}".format(item))
            lineto.append(j)
        for k in range(usecount):
            item = line[j].popleft()
    #print("行くべきは{0}".format(lineto))
    groupto = list(map(lambda x: group[x], lineto))
    if groupto is None:
        continue
    if len(groupto) == 0:
        #print("つながる先はないのでスキップ")
        continue
    if None in groupto:
        continue
    #print("つながるべきグループは{0}".format(groupto))
    if (max(groupto) - min(groupto)) > 2:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 1:
        #print("繋がれません")
        can = False
        break
    elif (max(groupto) - min(groupto)) == 2:
        target = (max(groupto) + min(groupto)) // 2
        #print("間に存在しないといけません。 {1} = {0}".format(target, i))
        group[i] = target
    else:
        # なるべく差が開いている方がに送る
        if (max(groupto) + 1) > group_max:
            target = max(groupto) + 1
            #print("maxを更新できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        elif (min(groupto) + 1) > group_min:
            target = min(groupto) - 1
            #print("minを後進できるのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1
        elif abs(max(groupto)) >= abs(min(groupto)):
            target = max(groupto) + 1
            #print("正のほうがおおきいか一緒なのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_max += 1
        else:
            target = min(groupto) - 1
            #print("負のほうが遠いのでそちらに追加(max, min) =  {0} = {1}なので{2} = {3}".format(max(groupto), min(groupto), i, target))
            group[i] = target
            group_min -= 1

group = group[1:]

if None in group:
    print(-1)
elif can:
    print(1 + max(group) - min(group))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(init):
  depth = 0
  groups = [INF for i in range(N)]
  q = deque()
  q.append(init)
  while len(q) > 0:
    u = q.popleft()
    groups[u] = depth
    for v in range(N):
      if M[u][v] == 0:
        continue
      if groups[v] != INF:
        if groups[v] == depth-1:
          continue
        else:
          return -1
      q.append(v)
    depth += 1
  return depth

N = int(input())
M = [list(map(int, list(input()))) for i in range(N)]
INF = 201

res = -1
for u in range(N):
  res = max(res, solve(u))

print(res)