wish 2008-10-15 03:51:00
点我顶贴
收藏
删除
郁闷额，写了个巨丑无比的“号称” O(n) 的算法（事实上常数很大）
而且貌似数据范围有问题，第一次直接按照题中范围结果普通保护错误。。。
第二次把 maxn、maxm、maxk 全部加到 100000 结果栈溢出。。。。
最后干脆把 dfs 改成 dfs 终于通过。。。
我的思路就是假定 1 号点的坐标是 (0, 0)，然后遍历一遍算出全部的坐标。判定 -1 的过程使用并查集完成。
另外还有一个疑问，貌似后面询问的 L 值是递增的？
我的算法要求它递增，我写了个 sort，出于好奇输出时的顺序并没有调整回 sort 之前的顺序，但是也通过了？
最后，20分求正解。。。（唉。。不是我抠，最多只让悬20。。。）
#1 guoshi3@2008-10-15 03:31:00
6859
回复
删除
正解不知道...
我的解法就是单纯的并差集。多存一点东西，就是某点和他父亲的坐标差。合并a，b两点的时候，根据a、b两点的坐标差以及他们到各自根的坐标差设rt1（a的根）和rt2（b的根）的坐标差。