为什么线性做法会被卡

P9869 [NOIP2023] 三值逻辑

说错了,带了反阿克曼函数,但这也几乎线性吧
by Rain_chr @ 2023-11-28 12:59:34


我把二分图判定的部分注释掉,他就不T了,但是我这个二分图判定不应该是 O(n+m)的吗?
by Rain_chr @ 2023-11-28 13:00:58


我又尝试注释掉二分图判定部分(dfs),只保留遍历图(color),但还是会T,难道每个点会访问不止一次?
by Rain_chr @ 2023-11-28 13:04:47


下了数据测了一下,以下是每组数据dfs和color共计运行次数: ``` #4 199633 216906 199846 207192 220538 206655 #6 300006 274118 300006 227993 245897 289515 ``` 并且#4的运行时间是1.8s,#6的运行时间是15.37s
by Rain_chr @ 2023-11-28 13:38:26


完了,col[i]=1;应该写成col[find(i)]=1的,此贴终结
by Rain_chr @ 2023-11-28 13:40:46


|