發表新討論
#19418:


lawrence910426@gmail.com (l4wr3nc3)

學校 : 新北市立板橋高級中學
編號 : 67988
來源 : [140.114.6.181]
最後登入時間 ：
2020-11-09 14:57:43
c522. 7. 迷你細胞 -- 2017高雄市資訊學科能力複賽 | From: [1.161.40.49] | 發表日期 : 2019-09-29 21:15

比較正式的作法

開持久化線段樹去維護啟發式並查集，再對時間軸二分搜

1. 合併時，O(lgN lgN)

2. 查詢時，O(lgM lgN lgN)

這時間複雜度聽起來就很毒瘤

-

離線大法才是王道

預設圖 G 空白，如果 (u,v) 連通，不理會他；如果 (u,v) 不連通，在圖 G 中加入一條權重為 time 的邊。

在圖 G 上建構 dfs tree，預處理。

 
#19419: Re:想法


lawrence910426@gmail.com (l4wr3nc3)

學校 : 新北市立板橋高級中學
編號 : 67988
來源 : [140.114.6.181]
最後登入時間 ：
2020-11-09 14:57:43
c522. 7. 迷你細胞 -- 2017高雄市資訊學科能力複賽 | From: [1.161.40.49] | 發表日期 : 2019-09-29 21:15

比較正式的作法

開持久化線段樹去維護啟發式並查集，再對時間軸二分搜

1. 合併時，O(lgN lgN)

2. 查詢時，O(lgM lgN lgN)

這時間複雜度聽起來就很毒瘤

-

離線大法才是王道

預設圖 G 空白，如果 (u,v) 連通，不理會他；如果 (u,v) 不連通，在圖 G 中加入一條權重為 time 的邊。

在圖 G 上建構 dfs tree，預處理。



許胖這篇也幫我刪掉好ㄇ ><

感恩 不要把我帳號刪掉

 
ZeroJudge Forum