結果
問題 | No.2301 Namorientation |
ユーザー | StanMarsh |
提出日時 | 2023-11-16 16:20:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,256 ms / 3,000 ms |
コード長 | 6,887 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 257,764 KB |
最終ジャッジ日時 | 2023-11-16 16:20:56 |
合計ジャッジ時間 | 28,864 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 153 ms
89,460 KB |
testcase_01 | AC | 154 ms
89,460 KB |
testcase_02 | AC | 152 ms
89,460 KB |
testcase_03 | AC | 153 ms
89,460 KB |
testcase_04 | AC | 153 ms
89,460 KB |
testcase_05 | AC | 156 ms
89,460 KB |
testcase_06 | AC | 156 ms
89,460 KB |
testcase_07 | AC | 154 ms
89,460 KB |
testcase_08 | AC | 153 ms
89,460 KB |
testcase_09 | AC | 153 ms
89,460 KB |
testcase_10 | AC | 154 ms
89,460 KB |
testcase_11 | AC | 155 ms
89,460 KB |
testcase_12 | AC | 787 ms
182,904 KB |
testcase_13 | AC | 709 ms
174,008 KB |
testcase_14 | AC | 1,198 ms
245,692 KB |
testcase_15 | AC | 843 ms
192,840 KB |
testcase_16 | AC | 1,008 ms
223,944 KB |
testcase_17 | AC | 769 ms
187,224 KB |
testcase_18 | AC | 1,085 ms
225,212 KB |
testcase_19 | AC | 663 ms
168,812 KB |
testcase_20 | AC | 1,037 ms
224,516 KB |
testcase_21 | AC | 867 ms
191,168 KB |
testcase_22 | AC | 604 ms
254,176 KB |
testcase_23 | AC | 578 ms
252,204 KB |
testcase_24 | AC | 514 ms
224,092 KB |
testcase_25 | AC | 501 ms
218,616 KB |
testcase_26 | AC | 598 ms
257,764 KB |
testcase_27 | AC | 1,254 ms
246,364 KB |
testcase_28 | AC | 1,231 ms
246,360 KB |
testcase_29 | AC | 1,256 ms
246,096 KB |
testcase_30 | AC | 1,254 ms
246,232 KB |
testcase_31 | AC | 1,238 ms
246,112 KB |
ソースコード
from random import getrandbits, randrange from string import ascii_lowercase, ascii_uppercase import sys from math import ceil, floor, sqrt, pi, factorial, gcd, log, log10, log2, inf, cos, sin from copy import deepcopy, copy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import ( accumulate, product, combinations, combinations_with_replacement, permutations, ) from bisect import bisect, bisect_left, bisect_right from functools import lru_cache, reduce from decimal import Decimal, getcontext from typing import List, Tuple, Optional inf = float("inf") def ceil_div(a, b): return (a + b - 1) // b def isqrt(num): res = int(sqrt(num)) while res * res > num: res -= 1 while (res + 1) * (res + 1) <= num: res += 1 return res def int1(s): return int(s) - 1 from types import GeneratorType def bootstrap(f, stack=[]): def wrapped(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrapped import sys import os input = lambda: sys.stdin.readline().rstrip("\r\n") print = lambda *args, end="\n", sep=" ": sys.stdout.write( sep.join(map(str, args)) + end ) def II(): return int(input()) def MII(base=0): return map(lambda s: int(s) - base, input().split()) def LII(base=0): return list(MII(base)) def NA(): n = II() a = LII() return n, a def read_graph(n, m, base=0, directed=False, return_edges=False): g = [[] for _ in range(n)] edges = [] for _ in range(m): a, b = MII(base) if return_edges: edges.append((a, b)) g[a].append(b) if not directed: g[b].append(a) if return_edges: return g, edges return g def read_graph_with_weight(n, m, base=0, directed=False, return_edges=False): g = [[] for _ in range(n)] edges = [] for _ in range(m): a, b, w = MII() a, b = a - base, b - base if return_edges: edges.append((a, b, w)) g[a].append((b, w)) if not directed: g[b].append((a, w)) if return_edges: return g, edges return g def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = None def NI(): global tokens if tokens is None: tokens = iterate_tokens() return int(next(tokens)) def LNI(n): return [NI() for _ in range(n)] def yes(res): print("Yes" if res else "No") def YES(res): print("YES" if res else "NO") def pairwise(a): n = len(a) for i in range(n - 1): yield a[i], a[i + 1] def factorial(n): return reduce(lambda x, y: x * y, range(1, n + 1)) def cmin(dp, i, x): if x < dp[i]: dp[i] = x def cmax(dp, i, x): if x > dp[i]: dp[i] = x def alp_a_to_i(s): return ord(s) - ord("a") def alp_A_to_i(s): return ord(s) - ord("A") def alp_i_to_a(i): return chr(ord("a") + i) def alp_i_to_A(i): return chr(ord("A") + i) d4 = [(1, 0), (0, 1), (-1, 0), (0, -1)] d8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)] def ranges(n, m): return ((i, j) for i in range(n) for j in range(m)) def valid(i, j, n, m): return 0 <= i < n and 0 <= j < m def ninj(i, j, n, m): return [(i + di, j + dj) for di, dj in d4 if valid(i + di, j + dj, n, m)] def gen(x, *args): if len(args) == 1: return [x] * args[0] if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]] if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]] if len(args) == 4: return [ [[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0] ] list2d = lambda a, b, v: [[v] * b for _ in range(a)] list3d = lambda a, b, c, v: [[[v] * c for _ in range(b)] for _ in range(a)] class Debug: def __init__(self, debug=False): self.debug = debug cur_path = os.path.dirname(os.path.abspath(__file__)) self.local = os.path.exists(cur_path + "/.cph") def get_ic(self): if self.debug and self.local: from icecream import ic return ic else: return lambda *args, **kwargs: ... from typing import List def Namori(g): n = len(g) cycle_edges = [set(g[i]) for i in range(n)] st = [] for p in range(n): if len(cycle_edges[p]) == 1: st.append(p) while st: p = st.pop() q = cycle_edges[p].pop() if p == q: cycle_edges[p].add(p) continue cycle_edges[q].remove(p) if len(cycle_edges[q]) == 1: st.append(q) visited = [0] * n cycles = [] for p in range(n): if visited[p] or len(cycle_edges[p]) == 0: continue next_set = [p] visited[p] = 1 cycle = [] while next_set: p = next_set.pop() cycle.append(p) for q in cycle_edges[p]: if visited[q]: continue visited[q] = 1 next_set.append(q) cycles.append(cycle) trees = [[] for _ in range(len(cycles))] for i in range(len(cycles)): for p in cycles[i]: next_set = [p] data = [] while next_set: p = next_set.pop() for q in g[p]: if visited[q]: continue visited[q] = 1 data.append((p, q)) next_set.append(q) trees[i].append((p, data)) return cycles, trees ic = Debug(1).get_ic() n = II() g, edges = read_graph(n, n, 1, False, True) ng = [set() for _ in range(n)] inCycle = [False] * n cycles, trees = Namori(g) for cycle in cycles: if len(cycle) == 1: continue for u in cycle: inCycle[u] = True for u, v in pairwise(cycle): ng[u].add(v) ng[cycle[-1]].add(cycle[0]) vst = [False] * n q = deque() for u in range(n): if inCycle[u]: vst[u] = True q.append(u) while q: u = q.popleft() for v in g[u]: if not inCycle[v] and not vst[v]: ng[v].add(u) vst[v] = True q.append(v) for u, v in edges: if v in ng[u]: print("->") else: print("<-")