結果

問題 No.1266 7 Colors
ユーザー tcltktcltk
提出日時 2021-01-21 15:41:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,225 ms / 3,000 ms
コード長 4,331 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 131,200 KB
最終ジャッジ日時 2024-06-06 21:20:41
合計ジャッジ時間 19,571 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 153 ms
88,704 KB
testcase_01 AC 153 ms
88,704 KB
testcase_02 AC 148 ms
88,960 KB
testcase_03 AC 566 ms
100,096 KB
testcase_04 AC 1,090 ms
122,272 KB
testcase_05 AC 611 ms
101,888 KB
testcase_06 AC 1,159 ms
125,824 KB
testcase_07 AC 1,225 ms
130,432 KB
testcase_08 AC 1,112 ms
123,136 KB
testcase_09 AC 988 ms
116,096 KB
testcase_10 AC 970 ms
113,152 KB
testcase_11 AC 758 ms
105,472 KB
testcase_12 AC 835 ms
107,648 KB
testcase_13 AC 911 ms
111,360 KB
testcase_14 AC 615 ms
102,016 KB
testcase_15 AC 1,216 ms
131,200 KB
testcase_16 AC 779 ms
107,392 KB
testcase_17 AC 1,191 ms
129,280 KB
testcase_18 AC 503 ms
130,816 KB
testcase_19 AC 488 ms
129,152 KB
testcase_20 AC 481 ms
129,280 KB
testcase_21 AC 265 ms
92,160 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#region Header
#!/usr/bin/env python3
# from typing import *

import sys
import io
import math
import collections
import decimal
import itertools
from queue import PriorityQueue
import bisect
import heapq

def input():
    return sys.stdin.readline()[:-1]

sys.setrecursionlimit(1000000)
#endregion

# _INPUT = """3 2 3
# 1010000
# 1000000
# 0010000
# 1 2
# 1 3
# 2 1 0
# 1 1 2
# 2 1 0
# """
# sys.stdin = io.StringIO(_INPUT)


# サイズを保持する Union-Find tree
class UnionFind():
    parents = []
    sizes = []
    count = 0

    def __init__(self, n):
        self.count = n
        self.parents = [i for i in range(n)]
        self.sizes = [1 for i in range(n)]

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i == root_j:
            return
        elif root_i < root_j:
            self.parents[root_j] = root_i
            self.sizes[root_i] += self.sizes[root_j]
        else:
            self.parents[root_i] = root_j
            self.sizes[root_j] += self.sizes[root_i]

    def same(self, i, j):
        return self.find(i) == self.find(j)

    def size(self, i):
        return self.sizes[self.find(i)]



# def dfs(G, colors, seen, city, color):
#     next_colors = set([color])
#     seen[city][color] = True
#     i = (color + 1) % 7
#     while colors[city][i] and (i not in next_colors):
#         if not seen[city][i]:
#             seen[city][i] = True
#             next_colors.add(i)
#         i = (i + 1) % 7
#     i = (color - 1) % 7
#     while colors[city][i] and (i not in next_colors):
#         if not seen[city][i]:
#             seen[city][i] = True
#             next_colors.add(i)
#         i = (i - 1) % 7

#     n = 0
#     for next_color in next_colors:
#         n += 1
#         for next_city in G[city]:
#             if colors[next_city][next_color] and (not seen[next_city][next_color]):
#                 n += dfs(G, colors, seen, next_city, next_color)

#     return n

def add_color(uf, N, G, colors, city, color):

    if colors[city][color]:
        return
    colors[city][color] = True

    i = (color + 1) % 7
    while colors[city][i] and (not uf.same(city * 7 + color, city * 7 + i)):
        uf.unite(city * 7 + color, city * 7 + i)
        i = (i + 1) % 7
    i = (color - 1) % 7
    while colors[city][i] and (not uf.same(city * 7 + color, city * 7 + i)):
        uf.unite(city * 7 + color, city * 7 + i)
        i = (i - 1) % 7

    for next_city in G[city]:
        if colors[next_city][color]:
            uf.unite(city * 7 + color, next_city * 7 + color)

def main():
    # N, M, Q = map(int, input().split())
    # colors = [None for _ in range(N)]
    # for i in range(N):
    #     s = input()
    #     colors[i] = [(s[j] == '1') for j in range(7)]
    # G = [list() for _ in range(N)]
    # for _ in range(M):
    #     _u, _v = map(int, input().split())
    #     G[_u-1].append(_v-1)
    #     G[_v-1].append(_u-1)

    # for _ in range(Q):
    #     t, x, y = map(int, input().split())
    #     if t == 1:
    #         colors[x-1][y-1] = True

    #     else:
    #         seen = [[False for _ in range(7)] for _ in range(N)]
    #         n = dfs(G, colors, seen, x-1, 0)
    #         print(n)

    N, M, Q = map(int, input().split())
    uf = UnionFind(N * 7)
    colors_s = [input() for _ in range(N)]

    G = [list() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)

    colors = [[False] * 7 for _ in range(N)]
    for city in range(N):
        for color in range(7):
            if colors_s[city][color] == '1':
                add_color(uf, N, G, colors, city, color)


    for _ in range(Q):
        t, x, y = map(int, input().split())
        if t == 1:
            add_color(uf, N, G, colors, x - 1, y - 1)

        else:
            n = uf.size((x - 1) * 7 + 0)
            print(n)


if __name__ == '__main__':
    main()
0