結果

問題 No.2301 Namorientation
ユーザー kyskys
提出日時 2023-05-13 17:06:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 885 ms / 3,000 ms
コード長 2,703 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 86,940 KB
実行使用メモリ 159,676 KB
最終ジャッジ日時 2023-08-19 15:32:54
合計ジャッジ時間 22,657 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
71,468 KB
testcase_01 AC 67 ms
71,368 KB
testcase_02 AC 66 ms
71,008 KB
testcase_03 AC 66 ms
71,252 KB
testcase_04 AC 67 ms
71,368 KB
testcase_05 AC 67 ms
71,432 KB
testcase_06 AC 68 ms
71,196 KB
testcase_07 AC 68 ms
71,208 KB
testcase_08 AC 67 ms
71,168 KB
testcase_09 AC 68 ms
71,228 KB
testcase_10 AC 69 ms
71,160 KB
testcase_11 AC 69 ms
71,264 KB
testcase_12 AC 543 ms
119,320 KB
testcase_13 AC 505 ms
116,904 KB
testcase_14 AC 885 ms
145,528 KB
testcase_15 AC 605 ms
124,496 KB
testcase_16 AC 668 ms
137,504 KB
testcase_17 AC 569 ms
122,620 KB
testcase_18 AC 719 ms
139,728 KB
testcase_19 AC 512 ms
115,228 KB
testcase_20 AC 714 ms
137,044 KB
testcase_21 AC 603 ms
123,532 KB
testcase_22 AC 274 ms
141,268 KB
testcase_23 AC 271 ms
140,240 KB
testcase_24 AC 245 ms
130,468 KB
testcase_25 AC 255 ms
142,396 KB
testcase_26 AC 337 ms
159,676 KB
testcase_27 AC 774 ms
145,960 KB
testcase_28 AC 767 ms
144,904 KB
testcase_29 AC 772 ms
145,592 KB
testcase_30 AC 771 ms
146,704 KB
testcase_31 AC 800 ms
145,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    class UnionFindTree:
        def __init__(self, initial_size:int) -> None:
            self.n_nodes = initial_size
            self.parents = [i for i in range(initial_size)]
            self.ranks = [0 for i in range(initial_size)]
            self.size = [1 for i in range(initial_size)]
            self.n_roots = initial_size
        def root(self, n:int) -> int:
            if self.parents[n] == n:
                return n
            else:
                self.parents[n] = self.root(self.parents[n])
                return self.parents[n]
        def same(self, n:int, m:int) -> bool:
            return (self.root(n) == self.root(m))
        def unite(self, n:int, m:int) -> None:
            if self.same(n, m):
                return
            self.n_roots -= 1
            n, m = self.root(n), self.root(m)
            if self.ranks[n] < self.ranks[m]:
                self.parents[n] = m
                self.size[m] += self.size[n]
            else:
                self.parents[m] = n
                self.size[n] += self.size[m]
                if self.ranks[n] == self.ranks[m]:
                    self.ranks[n] += 1
        def get_roots(self) -> set:
            return set([self.root(x) for x in range(self.n_nodes)])
        def count_roots(self) -> int:
            return self.n_roots
        def get_tree_size(self, n:int) -> int:
            return self.size[self.root(n)]
    N = iinput()
    g = [[] for _ in [0] * N]
    ans = [-1] * N
    uf = UnionFindTree(N)
    for i in range(N):
        a, b = mi0input()
        if uf.same(a, b):
            s = a
            ans[i] = '->'
            continue
        g[a].append((b, i, 0)) # <-
        g[b].append((a, i, 1)) # ->
        uf.unite(a, b)
    
    st = [s]
    seen = [False] * N
    seen[s] = True
    while st:
        u = st.pop()
        for v, idx, flg in g[u]:
            if seen[v]:
                continue
            seen[v] = True
            if flg:
                ans[idx] = '->'
            else:
                ans[idx] = '<-'
            st.append(v)

    for a in ans:
        print(a)


main()
0