結果

問題 No.3234 Infinite Propagation
コンテスト
ユーザー flippergo
提出日時 2026-05-19 09:55:11
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,448 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 182 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 878,908 KB
最終ジャッジ日時 2026-05-19 09:55:36
合計ジャッジ時間 7,707 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 3 WA * 5 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)
    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