Approach
Breadth-first search
For ABC067 D — Fennec VS. Snuke, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 63 lines of Python from the credited upstream file arc078_b.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def calc_dist(n, source, graph):5 from collections import deque6 7 dist = [0 for _ in range(n)]8 d = deque()9 d.append(source)10 visited = [False for _ in range(n)]11 visited[source] = True12 13 while d:14 di = d.popleft()15 16 for g in graph[di]:17 if visited[g]:18 continue19 20 visited[g] = True21 dist[g] = dist[di] + 122 d.append(g)23 24 return dist25 26 27def main():28 import sys29 30 input = sys.stdin.readline31 32 n = int(input())33 graph = [[] for _ in range(n)]34 35 for _ in range(n - 1):36 ai, bi = map(int, input().split())37 ai -= 138 bi -= 139 40 graph[ai].append(bi)41 graph[bi].append(ai)42 43 dist1 = calc_dist(n, 0, graph)44 dist2 = calc_dist(n, n - 1, graph)45 46 f_count = 047 s_count = 048 49 for fi, si in zip(dist1, dist2):50 if fi <= si:51 f_count += 152 else:53 s_count += 154 55 if f_count > s_count:56 print("Fennec")57 else:58 print("Snuke")59 60 61if __name__ == "__main__":62 main()63