CF1498E Two Houses 题解

可是我还真的不知道这个性质啊/kel

这题太麻森了，交互题不交互.jpg

考虑到图是一张竞赛图，竞赛图有下面的几条性质：

• 任意一个点入度加上出度为 $n-1$。
• 任意一张竞赛图缩点后一定为链。
• 若 $x$ 点的出度大于或等于 $y$ 点的出度，则 $x$ 一定可以到达 $y$。
• 同样的，若 $x$ 点的入度小于或等于 $y$ 点的入度，则 $x$ 一定可以到达 $y$。

然后这题就很简单了。考虑到对任意两个点 $x,y$，钦定 $x$ 的出度比 $y$ 的出度小，则根据性质 $3$ 可以知道一定存在路径使得 $y$ 可以到 $x$。此时只需要将所有二元组排序然后依次询问 $x,y$ 判断是否合法即可得到答案，时间复杂度为 $O(n^2\log n)$ 可以通过。

AC Code，很好写。