Approach
Depth-first search
For ABC256 E — Takahashi's Anguish, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 167 lines of Python from the credited upstream file abc256_e.py.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4import sys5import typing6 7sys.setrecursionlimit(10 ** 7)8 9 101112class SCCGraph:13 def __init__(self, n: int = 0) -> None:14 self._internal = _SCCGraph(n)15 16 def add_edge(self, from_vertex: int, to_vertex: int) -> None:17 n = self._internal.num_vertices()18 19 assert 0 <= from_vertex < n20 assert 0 <= to_vertex < n21 22 self._internal.add_edge(from_vertex, to_vertex)23 24 def scc(self) -> typing.List[typing.List[int]]:25 return self._internal.scc()26 27 28class CSR:29 def __init__(30 self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:31 self.start = [0] * (n + 1)32 self.elist = [0] * len(edges)33 34 for e in edges:35 self.start[e[0] + 1] += 136 37 for i in range(1, n + 1):38 self.start[i] += self.start[i - 1]39 40 counter = self.start.copy()41 42 for e in edges:43 self.elist[counter[e[0]]] = e[1]44 counter[e[0]] += 145 46 47class _SCCGraph:48 '''49 Reference:50 R. Tarjan,51 Depth-First Search and Linear Graph Algorithms52 '''53 54 def __init__(self, n: int) -> None:55 self._n = n56 self._edges: typing.List[typing.Tuple[int, int]] = []57 58 def num_vertices(self) -> int:59 return self._n60 61 def add_edge(self, from_vertex: int, to_vertex: int) -> None:62 self._edges.append((from_vertex, to_vertex))63 64 def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:65 g = CSR(self._n, self._edges)66 now_ord = 067 group_num = 068 visited = []69 low = [0] * self._n70 order = [-1] * self._n71 ids = [0] * self._n72 73 sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))74 75 def dfs(v: int) -> None:76 nonlocal now_ord77 nonlocal group_num78 nonlocal visited79 nonlocal low80 nonlocal order81 nonlocal ids82 83 low[v] = now_ord84 order[v] = now_ord85 now_ord += 186 visited.append(v)87 88 for i in range(g.start[v], g.start[v + 1]):89 to = g.elist[i]90 91 if order[to] == -1:92 dfs(to)93 low[v] = min(low[v], low[to])94 else:95 low[v] = min(low[v], order[to])96 97 if low[v] == order[v]:98 while True:99 u = visited[-1]100 visited.pop()101 order[u] = self._n102 ids[u] = group_num103 104 if u == v:105 break106 107 group_num += 1108 109 for i in range(self._n):110 if order[i] == -1:111 dfs(i)112 113 for i in range(self._n):114 ids[i] = group_num - 1 - ids[i]115 116 return group_num, ids117 118 def scc(self) -> typing.List[typing.List[int]]:119 ids = self.scc_ids()120 group_num = ids[0]121 counts = [0] * group_num122 123 for x in ids[1]:124 counts[x] += 1125 126 groups: typing.List[typing.List[int]] = [[] for _ in range(group_num)]127 128 for i in range(self._n):129 groups[ids[1][i]].append(i)130 131 return groups132 133 134def main():135 import sys136 137 input = sys.stdin.readline138 139 n = int(input())140 x = list(map(int, input().split()))141 c = list(map(int, input().split()))142 scc = SCCGraph(n)143 144 145 146 147 148 149 for i, xi in enumerate(x):150 xi -= 1151 scc.add_edge(i, xi)152 153 groups = scc.scc()154 ans = 0155 156 for group in groups:157 if len(group) == 1:158 continue159 160 ans += min([c[g] for g in group])161 162 print(ans)163 164 165if __name__ == "__main__":166 main()167