### zhiyangfan's blog

By zhiyangfan, history, 13 days ago,

`I am trying to solve https://codeforces.com/gym/103470/problem/K.

My solution is similar to the official tutorial(If you don't understand Chineses, it's ok! I write annotation in the code),but I'm troubled with constant factor(maybe not? If my time complexity is not good enough, please point out. qwq ), keeping getting TLE on test 38. :(

I wonder if someone can help me with it, pointing out something wrong with my implementations. qwq

• +1

 » 13 days ago, # |   +3 Your code has complexity $\Omega(\sum \deg^2)$ (which could be $\Omega(nm)$ worst case) for counting $C_3$ and $C_4$.
•  » » 13 days ago, # ^ |   0 Why? qwqI think my code is using the proper way of constructing the new graph and can decrease the time complexity to $\mathcal{O}(m\sqrt{m})$. qwq
•  » » » 13 days ago, # ^ |   0 Ahh, I'm sorry. You're probably right. Then you might want to remove the hash table since it's not very efficient.
•  » » » » 13 days ago, # ^ |   0 But without the hash I can't know how many times every edge is contained by $C_3$, for it requires a way to know the id of an edge with the vertices. qaq
•  » » » » » 13 days ago, # ^ | ← Rev. 2 →   +10 Just store the indices (such as changing the vector to vector >) while storing the endpoints owo
•  » » » » » » 13 days ago, # ^ |   0 That's amazing! Thank you so much for help!!