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:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            ab[i].append(j)

#print(ab)

st = -1

for i in range(n):
    if len(ab[i]) == 1:
        st = i
        break
    
if st == -1:
    print(-1)
    exit()
    
q = deque()
q.appendleft(st)

check = [0]*(n)
check[st] = 1

ans = 0
#print(st)

while len(q) > 0:
    #print(q)
    for i in range(len(q)):
        tmp = q.popleft()
        check[tmp] = 1
        cnt = 0
        #print(tmp,111111)
        li = []
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                q.append(ab[tmp][j])
                li.append(ab[tmp][j])
                
        for k in range(len(li)):
            for l in range(len(ab[li[k]])):
                for m in range(k+1,len(li)):
                    if ab[li[k]][l] == li[m]:
                        print(-1)
                        exit()
                
    ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")

def bfs(node):
    dist = [INF] * N
    dist[node] = 0
    union = [[] for _ in range(N+1)]
    union[0].append(node)
    q = deque()
    q.append(node)
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[curr] + 1 < dist[nxt]:
                dist[nxt] = dist[curr] + 1
                union[dist[nxt]].append(nxt)
                q.append(nxt)

    d = max(dist)
    max_idx = dist.index(d)
    return max_idx, dist, union

s, dist, union = bfs(0)

for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":
 
                    print(-1)
                    exit()

_, dist2, _ = bfs(s)
print(max(dist2) + 1)

Submission status: Wrong Answer

Solution code:

from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = deque()
q.append(0)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)

def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in es[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d

n, d = bfs(s)


print(d+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            ab[i].append(j)

#print(ab)

st = -1

for i in range(n):
    if len(ab[i]) == 1:
        st = i
        break
    
if st == -1:
    print(-1)
    exit()
    
q = deque()
q.appendleft(st)

check = [0]*(n)
check[st] = 1

ans = 0
#print(st)

while len(q) > 0:
    #print(q)
    for i in range(len(q)):
        tmp = q.popleft()
        for j in range(len(ab[tmp])):
            if check[ab[tmp][j]] == 0:
                q.append(ab[tmp][j])
                check[ab[tmp][j]] = 1
    ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = deque()
q.append(0)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)

dist = [INF] * N
dist[s] = 1
q = deque()
q.append(s)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1
        q.append(nxt)


print(max(dist))

Submission status: Wrong Answer

Solution code:


from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = deque()
q.append(0)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


c = -1
s = 0
for i in range(N):
    if dist[i] > c:
        c = dist[i]
        s = i

dist = [INF] * N
dist[s] = 1
q = deque()
q = deque()
q.append(s)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


print(max(dist))

Submission status: Wrong Answer

Solution code:

from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = deque()
q.append(0)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)


dist = [INF] * N
dist[s] = 1
q = deque()
q = deque()
q.append(s)

while q:
    curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= dist[curr] + 1:
            continue
        dist[nxt] = dist[curr] + 1

        union[dist[nxt]].append(nxt)
        q.append( nxt)


print(max(dist))

Submission status: Wrong Answer

Solution code:


from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = deque()
q.append((0, 0))

while q:
    cost, curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        q.append((dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)


dist = [INF] * N
dist[s] = 1
q = deque()
q.append((dist[s], s))

while q:
    cost, curr = q.popleft()
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        q.append((dist[nxt], nxt))


print(max(dist))

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            ab[i].append(j)

#print(ab)

st = -1

for i in range(n):
    if len(ab[i]) == 1:
        st = i
        break
    
if st == -1:
    print(-1)
    exit()
    
print(st)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            ab[i].append(j)

print(ab)

st = -1

for i in range(n):
    if len(ab[i]) == 1:
        st = i
        break
    
if st == -1:
    print(-1)
    exit()
    
print(st)

Submission status: Wrong Answer

Solution code:

import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)


dist = [INF] * N
dist[s] = 1
q = []
heapq.heappush(q, (dist[s], s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if cost + 1 < dist[nxt]:
            dist[nxt] = cost + 1
            heapq.heappush(q, (dist[nxt], nxt))

print(max(dist))

Submission status: Wrong Answer

Solution code:


import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)


dist = [INF] * N
dist[s] = 1
q = []
heapq.heappush(q, (dist[s], s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1
        heapq.heappush(q, (dist[nxt], nxt))

print(max(dist))

Submission status: Wrong Answer

Solution code:


import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


m = max(dist)
s = dist.index(m)


dist = [INF] * N
dist[s] = 0
q = []
heapq.heappush(q, (0, s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1
        heapq.heappush(q, (dist[nxt], nxt))

print(max(dist) + 1)

Submission status: Wrong Answer

Solution code:

import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()


c = 0
s = 0
for i in range(N):
    if dist[i] > c:
        s = i
        c = dist[i]


dist = [INF] * N
dist[s] = 0
q = []
heapq.heappush(q, (0, s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1
        heapq.heappush(q, (dist[nxt], nxt))

print(max(dist) + 1)

Submission status: Wrong Answer

Solution code:



import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in range(len(u)-1):
            for j in range(i+1,len(u)):
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[u[i]][u[j]] == "1":

                    print(-1)
                    exit()


c = 0
s = 0
for i in range(N):
    if dist[i] > c:
        s = i
        c = dist[i]


dist = [INF] * N
dist[s] = 0
q = []
heapq.heappush(q, (0, s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1
        heapq.heappush(q, (dist[nxt], nxt))

print(max(dist) + 1)

Submission status: Wrong Answer

Solution code:
import heapq



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)

"""
問題の理解が困難
ノードi,jを結ぶ辺があるとき、ノードiは集合aに、ノードjは集合k+1（あるいは逆）に含まれるようにノードを集合に分ける。
その条件を満たす最大の集合の数を求める

1->2
2->3
2->4
みたいなのがあるときに、
・1と2は別の集合（1を集合１、２を集合とする）
・２と３は別の集合（２が集合２なので、３は集合１か３。できるだけ集合の数を多くとりたいので、３とする）
・２と４は別の集合（２が集合２なので、４は集合１か３。上に同じく３とする）
みたいな感じか。
なので、
あるノードから等距離にあるノードを同じ集合にする
という戦略をとれば、集合の数を最大化できる。
で、同じ集合に属するやつらの間に辺がある場合、辺を挟んだノードは別の集合にならなければならないので矛盾するからNG

↑から、木の直径＋１が最大の集合数になるので、double sweepだったか？何かでもとめればよいか？
"""

INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in range(len(u)):
            for j in range(i+1,len(u)):
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[u[i]][u[j]] == "1":

                    print(-1)
                    exit()


c = 0
s = 0
for i in range(N):
    if dist[i] > c:
        s = i
        c = dist[i]


dist = [INF] * N
dist[s] = 0
q = []
heapq.heappush(q, (0, s))
while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1
        heapq.heappush(q, (dist[nxt], nxt))

print(max(dist) + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())
g=[[] for i in range(N)] 
cnt=0
for i in range(N):
  s=input()
  for j in range(N):
    if s[j]=='1':
      g[i].append(j)
      cnt+=1
w=cnt//2

color=[0]*N #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        elif color[g[v][i]]==0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True

def warshall(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

k=1
for i in range(N):
  if color[i]==0:
    if not f(i,1):
      k=-1

if k==0:
  print(-1)
else:
  d=[[float('inf')]*N for i in range(N)]
  for i in range(N):
    for j in g[i]:
      d[i][j]=1
  for i in range(N):
    d[i][i]=0
  A=warshall(d,N)
  ans=0
  for i in range(N):
    ans=max(ans,max(d[i]))
  print(ans+1)

Submission status: Wrong Answer

Solution code:
# 隣り合う頂点が、同じグループにいなければ良い
# 点を順番に0,1で塗っていき、既に0で塗られている場所に1を塗ろうとしたら（あるいはその逆）NG。

N = int(input())
E = [[] for i in range(N)]
G = [None] * N
INF = 10 ** 9
for i in range(N):
  edges = input()
  G[i] = list(map(int,list(edges)))
  G[i] = list(map(lambda x:INF if x == 0 else x,G[i]))
  for j in range(len(edges)):
    if edges[j] == "1":
      E[i].append(j)

color = [-1 for i in range(N)]
from collections import deque
q = deque([])
# 頂点、次に塗る色
q.append([0,0])

while q:
  v,bit = q.popleft()
  if color[v] != -1:
    # 既に色が塗られている
    if color[v] == bit: # 塗ろうとしている色と同じなら探索済み
      continue
    else: # 違う色ならNG
      print(-1)
      exit(0)
  # 塗る
  color[v] = bit
  children = E[v]
  for child in children:
    q.append([child,bit^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])

ans = 0
for i in range(N):
  for j in range(N):
    if ans < G[i][j]:
      ans = G[i][j]
      
print(ans + 1)

Submission status: Wrong Answer

Solution code:
# 隣り合う頂点が、同じグループにいなければ良い
# 点を順番に0,1で塗っていき、既に0で塗られている場所に1を塗ろうとしたら（あるいはその逆）NG。

N = int(input())
E = [[] for i in range(N)]
for i in range(N):
  edges = input()
  for j in range(len(edges)):
    if edges[j] == "1":
      E[i].append(j)

color = [-1 for i in range(N)]
from collections import deque
q = deque([])
# 頂点、次に塗る色
q.append([0,0])

while q:
  v,bit = q.popleft()
  if color[v] != -1:
    # 既に色が塗られている
    if color[v] == bit: # 塗ろうとしている色と同じなら探索済み
      continue
    else: # 違う色ならNG
      print(-1)
      exit(0)
  # 塗る
  color[v] = bit
  children = E[v]
  for child in children:
    q.append([child,bit^1])

# 頂点0から最も遠い頂点を求める
q = deque([])
# 頂点、距離
q.append([0,0])
longest_dist = 0
longest_v = -1
INF = 10 ** 9
visited = [INF for i in range(N)]
while q:
  v,dist = q.popleft()
  if visited[v] <= dist:
    continue
  visited[v] = dist
  if dist > longest_dist:
    longest_dist = dist
    longest_v = v
  children = E[v]
  for child in children:
    q.append([child,dist + 1])

q = deque()
q.append([longest_v,0])
visited = [INF for i in range(N)]
longest_dist = 0

while q:
  v,dist = q.popleft()
  if visited[v] <= dist:
    continue
  visited[v] = dist
  if longest_dist < dist:
    longest_dist = dist
  children = E[v]
  for child in children:
    q.append([child,dist + 1])
    
print(longest_dist + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
    for j, c in enumerate(input()):
        if c == '1':
            g[i].append(j)
d = [-1] * n
d[0] = 0
s = [0]
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            s.append(node)
            d[node] = d[p] ^ 1
        elif d[node] == d[p]:
            print(-1)
            exit(0)
ans = 0
for i in range(n):
    d = [-1] * n
    d[i] = 0
    s = [i]
    while s:
        p = s.pop()
        for node in g[p]:
            if d[node] == -1:
                s.append(node)
                d[node] = d[p] + 1
    ans = max(ans, max(d))
print(ans + 1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
s = nsn(n)

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

def ok(dist):
    for i in range(n):
        flag = False
        for j in range(n):
            for k in range(n):
                if dist[i][j] == 1 and dist[i][k] == 1 and dist[j][k] == 1:
                    flag = True
        if flag:
            return False
    return True

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == '1':
            dist[i][j] = 1
    dist[i][i] = 0

floyd_warshall(n, dist)

if ok(dist):
    ans = 0
    for i in range(n):
        for j in range(n):
            if dist[i][j] != inf:
                ans = max(dist[i][j], ans)
    print(ans + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = 0
for start in range(N):		
	cnt = np.zeros(N, dtype = np.int64)
	cnt[start] = 1
	q = [start]

	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				print(-1)
				sys.exit()
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def grouping(n, N, d):
    group = [-1]*(N+1)
    group[n] = 1

    q = [n]
    while q:
        s = q.pop()
        for t in d[s]:
            if group[t]!=-1:continue
            group[t] = group[s] + 1
            q.append(t)

    for k, v in d.items():
        for j in v:
            if not abs(group[j]-group[k])==1:
                return False
    
    return group


def solve():
    N = int(input())
    d = defaultdict(list)
    for i in range(1, N+1):
        for j, s in enumerate(input(), start=1):
            if s=="1":
                d[i].append(j)
    

    ans = -1
    for i in range(1, N+1):
        res = grouping(i, N, d)
        if res != False:
            ans = max(ans, max(res))
    
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
d=[[float("inf") for i in range(0,N)] for i in range(0,N)]
for i in range(0,N):
    S=input()
    for j in range(0,N):
        if S[j]=="1":
            d[i][j]=1

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

ans=0
for i in range(0,N):
    ans=max(ans,max(d[i]))
for i in range(1,N-1):
    for j in range(i+1,N):
        if d[i][j]==1 and d[0][i]==d[0][j]:
            ans=-2

print(ans+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
#   if not is_bt():
#     print(-1)
#     return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
colors = [0 for i in range(n)]
stack = [[0,1]]
flag = True
while len(stack) != 0:
    t = stack.pop()
    v = t[0]
    color = t[1]
    colors[v] = color
    for i in range(n):
        if S[v][i] == '1':
            if colors[i] == color:
                flag = False
                stack = []
                break
            else:
                if colors[i] == 0:
                    stack.append([i, -color])
if flag:
    maxdist = 0
    dist = []
    for i in range(n):
        d = [10**10]*n
        d[i] = 0
        dist.append(d)
    for i in range(n):
        for j in range(n):
            if S[i][j] == '1':
                dist[i][j] = 1
    for i in range(n):
        for k in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    for i in range(n):
        for j in range(n):
            maxdist = max(maxdist, dist[i][j])
    print(maxdist+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**10]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(n):
    for j in range(n):
        maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**10]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(n):
    for j in range(n):
        maxdist = max(maxdist, dist[i][j])
print(dist)