Official

D - Relative Position Editorial by en_translator


The coordinates can be obtained by performing a DFS (Depth-First Search) on a graph, with the people as the vertices and the vertex pairs \((A_i,B_i)\) given as the information as the edges.

We regard that each edge is a directed edge. For each edge form \(A_i\) to \(B_i\) and another from \(B_i\) to \(A_i\), store the relative position from the starting vertex to the ending vertex. In the DFS, maintain the current person’s index and coordinates, and update the coordinates every time we follow an edge.

Image

Writer’s solution (C++)

posted:
last update: