結果

問題 No.3234 Infinite Propagation
コンテスト
ユーザー flippergo
提出日時 2026-05-19 11:24:17
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 4,852 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 281 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 728,100 KB
最終ジャッジ日時 2026-05-19 11:24:50
合計ジャッジ時間 8,402 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

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

    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([])
                self.out_link.append(0)

            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]]) として、
            # fail 先で見つかるパターンを out[v] にコピーしていました。
            # しかしコピーすると同じ pattern_id が多くのノードに複製され、MLE の原因になります。
            # そこで out_link[v] に「fail をたどった先で、次に out があるノード」を覚えます。
            if self.out[self.fail[v]]:
                self.out_link[v] = self.fail[v]
            else:
                self.out_link[v] = self.out_link[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)

            # out_link をたどると、fail 先にあるパターンも見つけられます。
            # 例: "she" に到達したとき、out_link で "he" のノードへ進めば、
            # "she" の末尾にある "he" も検出できます。
            # out をコピーしていないので、メモリを増やさずに同じ判定ができます。
            u = self.out_link[v]
            while u != 0:
                for pattern_id in self.out[u]:
                    on_match(pattern_id)
                u = self.out_link[u]
    
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 = [[] for _ in range(N)]
        for i,t in enumerate(texts):
            seen = set()

            def add_edge(j):
                # 同じ Y_i の中で同じ X_j が何度見つかっても、
                # グラフの辺 i -> j は 1 本あれば十分です。
                # seen はこの Y_i を処理している間だけ使い、次の i では捨てます。
                if j not in seen:
                    seen.add(j)
                    G[i].append(j)

            ac.search(t, add_edge)
        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