結果

問題 No.274 The Wall
ユーザー lam6er
提出日時 2025-03-31 17:36:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,579 ms / 2,000 ms
コード長 3,543 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 322,736 KB
最終ジャッジ日時 2025-03-31 17:37:35
合計ジャッジ時間 9,253 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

def main():
    N, M = map(int, stdin.readline().split())
    blocks = []
    for _ in range(N):
        L, R = map(int, stdin.readline().split())
        flipped_L = (M - 1) - R
        flipped_R = (M - 1) - L
        original = (L, R)
        flipped = (flipped_L, flipped_R)
        blocks.append((original, flipped))

    # Build implication graph
    adj = [[] for _ in range(2 * N)]  # 2N literals (var and neg)
    for i in range(N):
        for j in range(i + 1, N):
            block_i = blocks[i]
            block_j = blocks[j]
            for a in [0, 1]:
                i_start, i_end = block_i[a]
                for b in [0, 1]:
                    j_start, j_end = block_j[b]
                    # Check overlap
                    overlap = not (i_end < j_start or j_end < i_start)
                    if overlap:
                        # Compute literals for the clause
                        if a == 1:
                            l_i = 2 * i + 1  # ~var_i
                        else:
                            l_i = 2 * i      # var_i
                        if b == 1:
                            l_j = 2 * j + 1  # ~var_j
                        else:
                            l_j = 2 * j      # var_j
                        # Add implications: ~l_i -> l_j and ~l_j -> l_i
                        # Edge 1: ~l_i -> l_j
                        complement_l_i = l_i ^ 1
                        adj[complement_l_i].append(l_j)
                        # Edge 2: ~l_j -> l_i
                        complement_l_j = l_j ^ 1
                        adj[complement_l_j].append(l_i)

    # Tarjan's algorithm to find SCC iteratively
    index = 0
    indices = [-1] * (2 * N)
    low = [0] * (2 * N)
    in_stack = [False] * (2 * N)
    scc_id = [0] * (2 * N)
    scc_count = 0
    stack = []
    for u in range(2 * N):
        if indices[u] == -1:
            stack_ = [(u, iter(adj[u]))]
            indices[u] = index
            low[u] = index
            index += 1
            path = [u]
            in_stack[u] = True
            dfs_stack = []
            while stack_:
                node, neighbors = stack_[-1]
                try:
                    v = next(neighbors)
                    if indices[v] == -1:
                        indices[v] = index
                        low[v] = index
                        index += 1
                        stack_.append((v, iter(adj[v])))
                        path.append(v)
                        in_stack[v] = True
                    else:
                        if in_stack[v]:
                            low[node] = min(low[node], indices[v])
                except StopIteration:
                    stack_.pop()
                    if stack_:
                        parent = stack_[-1][0]
                        low[parent] = min(low[parent], low[node])
                    if low[node] == indices[node]:
                        while True:
                            w = path.pop()
                            in_stack[w] = False
                            scc_id[w] = scc_count
                            if w == node:
                                break
                        scc_count += 1

    # Check for any variable and its negation in the same SCC
    possible = True
    for i in range(N):
        if scc_id[2 * i] == scc_id[2 * i + 1]:
            possible = False
            break
    print("YES" if possible else "NO")

if __name__ == "__main__":
    main()
0