結果

問題 No.1266 7 Colors
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-10-23 23:12:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 849 ms / 3,000 ms
コード長 1,915 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 161,176 KB
最終ジャッジ日時 2024-07-21 12:36:13
合計ジャッジ時間 13,902 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/1266

頂点を7倍する
→行ける頂点数になる

N*C+v を頂点番号とする

"""

from sys import stdin

def uf_find(n):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b):

    ap = uf_find(a)
    bp = uf_find(b)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            vnum[ap] += vnum[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            vnum[bp] += vnum[ap]
        else:
            p[bp] = ap
            rank[ap] += 1
            vnum[ap] += vnum[bp]

        return False

N,M,Q = map(int,stdin.readline().split())

exist = [False] * (7*N)
p = [i for i in range(7*N)]
rank = [0] * (7*N)
vnum = [1] * (7*N)

slis = []
for i in range(N):
    s = list(stdin.readline()[:-1])
    for j in range(7):
        if s[j] == "1":
            exist[N*j+i] = True
            if s[j] == "1" and s[(j+1)%7] == "1":
                k = (j+1)%7
                uf_union(N*j+i , N*k+i)
    slis.append(s)

lis = [ [] for i in range(N) ]
for i in range(M):
    v,u = map(int,stdin.readline().split())
    v -= 1
    u -= 1
    for j in range(7):
        if exist[N*j+v] and exist[N*j+u]:
            uf_union(N*j+v,N*j+u)
    lis[v].append(u)
    lis[u].append(v)

ans = []
for loop in range(Q):
    tp,x,y = map(int,stdin.readline().split())
    x -= 1
    y -= 1
    if tp == 1:
        exist[N*y+x] = True
        for nex in lis[x]:
            if exist[N*y+nex]:
                uf_union(N*y+x,N*y+nex)
        if slis[x][(y-1)%7] == "1":
            k = (y-1)%7
            uf_union(N*y+x,N*k+x)
        if slis[x][(y+1)%7] == "1":
            k = (y+1)%7
            uf_union(N*y+x,N*k+x)
        slis[x][y] = "1"
    else:
        ans.append( vnum[uf_find(x)] )
print ("\n".join(map(str,ans)))
0