`I am trying to solve https://mirror.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
Your code has complexity $$$\Omega(\sum \deg^2)$$$ (which could be $$$\Omega(nm)$$$ worst case) for counting $$$C_3$$$ and $$$C_4$$$.
Why? qwq
I 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
Ahh, I'm sorry. You're probably right. Then you might want to remove the hash table since it's not very efficient.
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
Just store the indices (such as changing the vector to vector<pair<int, int> >) while storing the endpoints owo
That's amazing! Thank you so much for help!!