Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

为什么用tarjan的方法看不出效果来？郁闷

Posted by mmd at 2007-10-06 22:05:52 on Problem 3417
In Reply To:借路问一下牛人们怎么把lca写的那么快的。我试了两种方法都比较慢。 Posted by:mmd at 2007-10-06 22:03:46

Followed by:

Online的那个？ (0) cuiaoxiang 2007-10-06 22:07:43
- offline那个 (0) mmd 2007-10-06 22:08:00
去掉了并查集的union操作，去掉了ancestor数组，去掉了乱七八糟会慢的东西，怎么还这么慢。 (0) mmd 2007-10-06 22:09:14
- 还有findFather操作也改成非递归的了 (0) mmd 2007-10-06 22:09:45
  - 其实find_father这个根据偶以前的实验递归的也不慢大概是除了第一次以后都只递归一两次 (0) cuiaoxiang 2007-10-06 22:12:34
- 难道他们使用了O(n) 的rmq (0) cuiaoxiang 2007-10-06 22:11:20
  - 那个不是更慢吗？询问这么多，估计更慢吧。 (0) mmd 2007-10-06 22:12:03
    - 悄悄地找个网吧试他们的密码 -。- (0) cuiaoxiang 2007-10-06 22:14:06
      - -_-!去找个代理。。。网吧太贵了。 (0) mmd 2007-10-06 22:15:52
      - -_-!! (0) ogogo 2007-10-06 22:15:57
      - Re:悄悄地找个网吧试他们的密码 -。- 啊哈哈 (0) sunny_fable 2007-10-06 22:56:08
    - 我用的rmq求lca,600多ms过了 (0) woodfish 2007-10-09 09:41:28

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator