結果

問題 No.3234 Infinite Propagation
コンテスト
ユーザー flippergo
提出日時 2026-05-19 10:39:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 3,526 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,157 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 1,342,564 KB
最終ジャッジ日時 2026-05-19 10:39:44
合計ジャッジ時間 5,974 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 MLE * 2 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

class AhoCorasick:
    def __init__(self):
        self.next = [dict()]
        self.fail = [0]
        self.out = [[]]

    def add(self, pattern: str, pattern_id: int) -> None:
        v = 0

        for ch in pattern:
            if ch not in self.next[v]:
                new_node = len(self.next)
                self.next[v][ch] = new_node
                self.next.append(dict())
                self.fail.append(0)
                self.out.append([])

            v = self.next[v][ch]

        self.out[v].append(pattern_id)

    def build(self) -> None:
        q = deque()

        for ch, u in self.next[0].items():
            self.fail[u] = 0
            q.append(u)

        while q:
            v = q.popleft()

            self.out[v].extend(self.out[self.fail[v]])

            for ch, u in self.next[v].items():
                f = self.fail[v]

                while f != 0 and ch not in self.next[f]:
                    f = self.fail[f]

                if ch in self.next[f]:
                    self.fail[u] = self.next[f][ch]
                else:
                    self.fail[u] = 0

                q.append(u)

    def search(self, text: str, on_match) -> None:
        v = 0

        for pos, ch in enumerate(text):
            while v != 0 and ch not in self.next[v]:
                v = self.fail[v]

            if ch in self.next[v]:
                v = self.next[v][ch]
            else:
                v = 0

            for pattern_id in self.out[v]:
                # 見つかった結果をリストにためず、その場で呼び出し側に渡します。
                # この問題では「どの位置で見つかったか」は不要なので、
                # pattern_id だけを渡せば十分です。
                on_match(pattern_id)
    
T = int(input())
for _ in range(T):
    N = int(input())
    patterns = []
    texts = []
    for _ in range(N):
        x,y = input().split()
        patterns.append(x)
        texts.append(y)
    if "a" not in patterns:
        print("No")
    else:
        ac = AhoCorasick()
        for i,p in enumerate(patterns):
            ac.add(p, i)
        ac.build()
        G = {i:[] for i in range(N)}
        for i,t in enumerate(texts):
            # ac.search(t, G[i].append) と書くと、
            # X_j が Y_i の中で見つかるたびに G[i].append(j) がすぐ実行されます。
            # そのため、matches のような大きな一時リストを作らずに済みます。
            ac.search(t, G[i].append)
        que = deque()
        A = set()
        for i,pattern in enumerate(patterns):
            if pattern == "a":
                que.append(i)
                A.add(i)
        while que:
            u = que.popleft()
            for v in G[u]:
                if v not in A:
                    A.add(v)
                    que.append(v)
        F = {i:[] for i in range(N)}
        B = {i:0 for i in A}
        for i in A:
            for v in G[i]:
                if v in A:
                    F[i].append(v)
                    B[v] += 1
        que = deque()
        for v in B:
            if B[v] == 0:
                que.append(v)
        while que:
            u = que.popleft()
            for v in F[u]:
                B[v] -= 1
                if B[v] == 0:
                    que.append(v)
        flag = 0
        for v in B:
            flag += B[v]
        if flag==0:
            print("No")
        else:
            print("Yes")
0