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

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
#print(group)

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

Solution code:
sin/agc039 >>> cat b.py 
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
S = [input().strip() for _ in range(N)]
C = [0]*N

flg = False
for sp, row in enumerate(S):
    if flg:
        break

    if row.count('1') == 1 or sp == len(S)-1:
        flg = True

        # start BFS
        C[sp] = 1
        q = deque([])
        for i, v in enumerate(row):
            if v == '1':
                q.append(int(i))

        cnt = 0 # length
        c = -1 # color
        while q:
            cnt += 1
            for i in range(len(q)):
                np_ind = q.popleft()
                if C[np_ind] == -c:
                    print(-1)
                    exit()
                elif C[np_ind] == c:
                    pass
                else:
                    C[np_ind] = c
                    for i, v in enumerate(S[np_ind]):
                        if v == '1':
                            q.append(int(i))
            c *= -1

print(cnt)

Submission status: Runtime Error

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
#print(group)

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 can:
    print(1 + max(group) - min(group))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]
node_set = [ None for i in range(n)]
color_list = [ "White" for i in range(n) ]
search_list = [0]
node_set[0] = 0
color_list[0] = "Black"

ans = 2
while search_list != []:
    new_search_list = []
    for i in search_list:
        for j, v in enumerate(connect_matrix[i]):
            if v == "1" and color_list[j] == "White":
                if node_set[j] is None:
                    node_set[j] = node_set[i] + 1

                new_search_list.append(j)
                color_list[j] = "Black"
            else:
                if (node_set[j] + node_set[i]) % 2 == 0:
                    ans = -1
    search_list = new_search_list

print(ans)

Submission status: Runtime Error

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
if testc > 1:
    check = check[0]

for i in check:
    tres = 1
    flag = [-2 for i 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: Runtime Error

Solution code:
import collections, itertools


class UnionFind():
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

    def is_same(self, x, y):
        find = self.find
        return find(x) == find(y)

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

    def size(self, x):
        return self.SIZE[self.find(x)]


N = int(input())
S = [[int(_) for _ in input()] for _ in range(N)]
G = collections.defaultdict(set)
for i, j in itertools.product(range(N), repeat=2):
    if S[i][j]:
        G[i].add(j)
P = [-1] * N
P[0] = -2
D = [-10] * N
D[0] = 0
Q = collections.deque([0])
UF = UnionFind(N)
while Q:
    x = Q.popleft()
    Gx = list(G[x])
    for y in Gx:
        if P[x] == y:
            continue
        if D[y] == -10:
            D[y] = D[x] + 1
            P[y] = x
            Q += [y]
        else:
            G[x].remove(y)
            if D[x] > D[y]:
                x, y = y, x
            cy1 = [y]
            cy2 = [x]
            for _ in range(D[y] - D[x]):
                cy1 += [P[cy1[-1]]]
            while True:
                cy1 += [P[cy1[-1]]]
                cy2 += [P[cy2[-1]]]
                if cy1[-1] == cy2[-1]:
                    break
            cy = cy1[-2::-1] + cy2
            if len(cy) % 2:
                print(-1)
                exit()
            c1 = cy[0]
            c2 = cy[1]
            for ca, cb in zip(cy[::2], cy[1::2]):
                UF.unite(c1, ca)
                UF.unite(c2, cb)
UF.scan_uf()
print(len(set(UF.dat)))

Submission status: Runtime Error

Solution code:
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[[] for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l[i].append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
while 0 in visited:
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

Submission status: Runtime Error

Solution code:

n = int(input())
S = [list(input()) for i in range(n)]

M = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j] == "1":
            M[i].append(j)
ans = -1
owa = 0
for i in range(n):
    a0 = -1
    Q = [[0] * 2 for i in range(n*n+3)]
    Q[0] = [i, 0]
    st = 0
    ri = 1
    D = [-1] * n
    while st < ri:
        a = Q[st][0]
        d = Q[st][1]
        D[a] = d
        for x in M[a]:
            if D[x] == -1:
                Q[ri] = [x, d+1]
                ri += 1
            elif D[x] != d-1 and D[x] != d+1:
                owa = 1
                break
        if owa == 1:
            break
        st += 1
    if owa == 0:
        a0 = max(D)+1
    ans = max(ans, a0)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
s = [input() for i in range(n)]
q = deque([0])
d = [float('inf')] * n
d[0] = 0
while q:
    p = q.popleft()
    for i, c in enumerate(s[p]):
        if c == '1' and d[i] == float('inf'):
            d[i] = d[p] + 1
            q.append(i)
m = 0
for i in range(n):
    if d[m] < d[i]:
        m = i
q = deque([m])
d = [float('inf')] * n
d[m] = 0
while q:
    p = q.popleft()
    for i, c in enumerate(s[p]):
        if c == '1':
            if d[i] == float('inf'):
                d[i] = d[p] + 1
                q.append(i)
            elif d[i] != d[p] + 1 and d[i] != d[p] - 1:
                print(-1)
                exit(1)
m = 0
for i in range(n):
    m = max(m, d[i])
print(m + 1)

Submission status: Runtime Error

Solution code:

n = int(input())
S = [list(input()) for i in range(n)]

M = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j] == "1":
            M[i].append(j)
ans = -1
owa = 0
for i in range(n):
    a0 = -1
    Q = [[0] * 2 for i in range(n+3)]
    Q[0] = [i, 0]
    st = 0
    ri = 1
    D = [-1] * n
    while st < ri:
        a = Q[st][0]
        d = Q[st][1]
        D[a] = d
        for x in M[a]:
            if D[x] == -1:
                Q[ri] = [x, d+1]
                ri += 1
            elif D[x] != d-1 and D[x] != d+1:
                owa = 1
                break
        if owa == 1:
            break
        st += 1
    if owa == 0:
        a0 = max(D)+1
    ans = max(ans, a0)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)

def is_bipartite():
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True
if is_bipartite()==0:
  print(-1)
  sys.exit()

for i in range(len(es)):
  if len(es[i])==1:
    x=i
    break
connection=es
distance1=[-1 for i in range(n)]
distance1[x]=0
next=connection[x]
next2=[]
check=[-1 for i in range(n)]
check[x]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

print(max(distance1)+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()

for i in range(len(es)):
  if len(es[i])==1:
    x=i
connection=es
distance1=[-1 for i in range(n)]
distance1[x]=0
next=connection[x]
next2=[]
check=[-1 for i in range(n)]
check[x]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

print(max(distance1)+1)

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
using namespace std;
#ifdef ONLINE_JUDGE
#define trace(...)
#endif

using LL = long long;

const int N = 210;
bool adj[N][N];
int dis[N];
bool done[N];

int solve(int root, int n) {
	fill(dis, dis + n, N);
	fill(done, done + n, false);
	queue<int> Q;
	Q.push(root); dis[root] = 1; 

	int ans = 1;
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		if (done[u]) continue;
		done[u] = true;
		for (int v = 0; v < n; v++) {
			if (adj[u][v]) {
				if (dis[v] == N) {
					dis[v] = dis[u] + 1;
					Q.push(v);
					ans = max(ans, dis[v]);
				}
				if (abs(dis[u] - dis[v]) != 1) return -1;
			}
		}
	}
	// for (int u = 0; u < n; u++) {
	// 	for (int v = 0; v < n; v++) {
	// 		if (adj[u][v] && abs(dis[u] - dis[v]) != 1) return -1;
	// 	}
	// }
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		string line; cin >> line;
		for (int j = 0; j < n; j++) {
			adj[i][j] = line[j] == '1';
		}
	}

	int ans = -1;
	for (int u = 0; u < n; u++) {
		ans = max(ans, solve(u, n));
	}
	cout << ans << endl;

	return 0;
}