結果

問題 No.274 The Wall
ユーザー zkou
提出日時 2021-03-12 19:32:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 6,440 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 77,344 KB
最終ジャッジ日時 2024-10-14 09:45:17
合計ジャッジ時間 3,091 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class _csr:
    def __init__(self, n, edges):
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)
        for v, _ in edges:
            self.start[v + 1] += 1
        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]
        counter = self.start.copy()
        for v, e in edges:
            self.elist[counter[v]] = e
            counter[v] += 1
class scc_graph:
    """It calculates the strongly connected components of directed graphs.
    """
    def __init__(self, n):
        """It creates a directed graph with n vertices and 0 edges.
        Constraints
        -----------
        >   0 <= n <= 10 ** 8
        Complexity
        ----------
        >   O(n)
        """
        self.n = n
        self.edges = []
    def add_edge(self, from_, to):
        """It adds a directed edge from the vertex `from_` to the vertex `to`.
        Constraints
        -----------
        >   0 <= from_ < n
        >   0 <= to < n
        Complexity
        ----------
        >   O(1) amortized
        """
        assert 0 <= from_ < self.n
        assert 0 <= to < self.n
        self.edges.append((from_, to))
    def _scc_ids(self):
        g = _csr(self.n, self.edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self.n
        order = [-1] * self.n
        ids = [0] * self.n
        parent = [-1] * self.n
        stack = []
        for i in range(self.n):
            if order[i] == -1:
                stack.append(i)
                stack.append(i)
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        visited.append(v)
                        for i in range(g.start[v], g.start[v + 1]):
                            to = g.elist[i]
                            if order[to] == -1:
                                stack.append(to)
                                stack.append(to)
                                parent[to] = v
                            else:
                                low[v] = min(low[v], order[to])
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.n
                                ids[u] = group_num
                                if u == v:
                                    break
                            group_num += 1
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])
        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x
        return group_num, ids
    def scc(self):
        """It returns the list of the "list of the vertices" that satisfies the following.
        >   Each vertex is in exactly one "list of the vertices".
        >   Each "list of the vertices" corresponds to the vertex set of a strongly connected component. 
        The order of the vertices in the list is undefined.
        >   The list of "list of the vertices" are sorted in topological order, 
        i.e., for two vertices u, v in different strongly connected components, 
        if there is a directed path from u to v, 
        the list contains u appears earlier than the list contains v.
        Complexity
        ----------
        >   O(n + m), where m is the number of added edges. 
        """
        group_num, ids = self._scc_ids()
        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)
        return groups
class two_sat:
    """It solves 2-SAT.
    For variables x[0], x[1], ..., x[n-1] and clauses with form
    >   ((x[i] = f) or (x[j] = g)),
    it decides whether there is a truth assignment that satisfies all clauses.
    """
    def __init__(self, n):
        """It creates a 2-SAT of n variables and 0 clauses.
        Constraints
        -----------
        >   0 <= n <= 10 ** 8
        Complexity
        ----------
        >   O(n)
        """
        self.n = n
        self._answer = [False] * n
        self.scc = scc_graph(2 * n)
    def add_clause(self, i, f, j, g):
        """It adds a clause ((x[i] = f) or (x[j] = g)).
        Constraints
        -----------
        >   0 <= i < n
        >   0 <= j < n
        Complexity
        ----------
        >   O(1) amortized
        """
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        self.scc.add_edge(2 * i + (f == 0), 2 * j + (g == 1))
        self.scc.add_edge(2 * j + (g == 0), 2 * i + (f == 1))
    def satisfiable(self):
        """If there is a truth assignment that satisfies all clauses, it returns `True`. 
        Otherwise, it returns `False`.
        Constraints
        -----------
        >   You may call it multiple times.
        Complexity
        ----------
        >   O(n + m), where m is the number of added clauses.
        """
        _, ids = self.scc._scc_ids()
        for i in range(self.n):
            if ids[2 * i] == ids[2 * i + 1]:
                return False
            self._answer[i] = (ids[2*i] < ids[2*i+1])
        return True
    def answer(self):
        """It returns a truth assignment that satisfies all clauses of the last call of `satisfiable`.
        If we call it before calling `satisfiable` or when the last call of `satisfiable` returns `False`, 
        it returns the list of length n with undefined elements.
        Complexity
        ----------
        >   O(n) 
        """
        return self._answer.copy()
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    LRs = [tuple(map(int, input().split())) for _ in range(N)]
    ts = two_sat(N)
    for i in range(N):
        Li, Ri = LRs[i]
        for j in range(i + 1, N):
            Lj, Rj = LRs[j]
            f1 = not (Ri < Lj or Rj < Li)
            f2 = not (M - 1 - Li < Lj or Rj < M - 1 - Ri)
            if f1 and f2:
                print("NO")
                exit()
            if f1:
                ts.add_clause(i, 0, j, 0)
                ts.add_clause(i, 1, j, 1)
            if f2:
                ts.add_clause(i, 0, j, 1)
                ts.add_clause(i, 1, j, 0)
    print("YES" if ts.satisfiable() else "NO")
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0