pqAp
洛谷
考虑暴力怎么做。
这个本质上就是一个最长路的问题，所以考虑对于三种门都暴力建图，复杂度为 \(O(n^2)\)，但是据说可以过？
其实，只需要对于非空的行/列建立一个超级点，然后将它连向那一行/列的所有点，对于有横天门或纵寰门的点，连向对应行的虚拟点即可。
对于任意门，暴力即可。
点数最多是 \(3n\)（因为最坏情况是没有两个点的横纵坐标其一相等），边数最多是 \(10n\)（都是任意门+虚拟点向点连的边）。
复杂度 \(O(n)\)（附带大常数）。
考虑暴力怎么做。
这个本质上就是一个最长路的问题，所以考虑对于三种门都暴力建图，复杂度为 \(O(n^2)\)，但是据说可以过？
其实，只需要对于非空的行/列建立一个超级点，然后将它连向那一行/列的所有点，对于有横天门或纵寰门的点，连向对应行的虚拟点即可。
对于任意门，暴力即可。
点数最多是 \(3n\)（因为最坏情况是没有两个点的横纵坐标其一相等），边数最多是 \(10n\)（都是任意门+虚拟点向点连的边）。
复杂度 \(O(n)\)（附带大常数）。