結果

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

ソースコード

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):
        v = 0
        result = []

        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]:
                result.append((pos, pattern_id))

        return result
    
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)}
        inDeg = [0 for _ in range(N)]
        for i,t in enumerate(texts):
            matches = ac.search(t)
            for end_pos, pattern_id in matches:
                G[i].append(pattern_id)
                inDeg[pattern_id] += 1
        que = deque()
        for i in range(N):
            if inDeg[i] == 0:
                que.append(i)
        while que:
            v = que.popleft()
            for u in G[v]:
                inDeg[u] -= 1
                if inDeg[u] == 0:
                    que.append(u)
        if sum(inDeg)==0:
            print("No")
        else:
            print("Yes")
0