結果

問題 No.1266 7 Colors
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-10-23 23:12:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,072 ms / 3,000 ms
コード長 1,915 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 87,076 KB
実行使用メモリ 161,848 KB
最終ジャッジ日時 2023-09-28 17:56:33
合計ジャッジ時間 17,809 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
71,184 KB
testcase_01 AC 73 ms
71,132 KB
testcase_02 AC 76 ms
71,424 KB
testcase_03 AC 674 ms
98,092 KB
testcase_04 AC 985 ms
133,280 KB
testcase_05 AC 706 ms
100,756 KB
testcase_06 AC 993 ms
140,048 KB
testcase_07 AC 1,055 ms
147,440 KB
testcase_08 AC 966 ms
135,756 KB
testcase_09 AC 874 ms
121,884 KB
testcase_10 AC 868 ms
118,152 KB
testcase_11 AC 729 ms
104,760 KB
testcase_12 AC 829 ms
108,940 KB
testcase_13 AC 836 ms
112,496 KB
testcase_14 AC 711 ms
100,072 KB
testcase_15 AC 1,072 ms
150,936 KB
testcase_16 AC 846 ms
110,452 KB
testcase_17 AC 1,049 ms
146,496 KB
testcase_18 AC 642 ms
161,848 KB
testcase_19 AC 663 ms
151,096 KB
testcase_20 AC 661 ms
150,580 KB
testcase_21 AC 221 ms
86,700 KB
権限があれば一括ダウンロードができます

ソースコード

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