結果

問題 No.1266 7 Colors
ユーザー tcltktcltk
提出日時 2021-01-21 15:41:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,110 ms / 3,000 ms
コード長 4,331 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 87,000 KB
実行使用メモリ 128,712 KB
最終ジャッジ日時 2023-08-26 02:26:32
合計ジャッジ時間 18,557 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 190 ms
83,196 KB
testcase_01 AC 192 ms
82,952 KB
testcase_02 AC 197 ms
82,780 KB
testcase_03 AC 509 ms
95,772 KB
testcase_04 AC 952 ms
120,384 KB
testcase_05 AC 532 ms
98,868 KB
testcase_06 AC 1,020 ms
124,592 KB
testcase_07 AC 1,110 ms
128,380 KB
testcase_08 AC 961 ms
121,160 KB
testcase_09 AC 823 ms
113,256 KB
testcase_10 AC 823 ms
110,840 KB
testcase_11 AC 660 ms
101,724 KB
testcase_12 AC 711 ms
105,600 KB
testcase_13 AC 776 ms
108,752 KB
testcase_14 AC 542 ms
98,228 KB
testcase_15 AC 1,065 ms
128,712 KB
testcase_16 AC 680 ms
104,960 KB
testcase_17 AC 1,037 ms
127,664 KB
testcase_18 AC 457 ms
126,416 KB
testcase_19 AC 452 ms
124,576 KB
testcase_20 AC 440 ms
124,388 KB
testcase_21 AC 284 ms
88,692 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