zhiyangfan's blog

By zhiyangfan, history, 3 years ago, In English

`I am trying to solve https://codeforces.net/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

My code.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your code has complexity $$$\Omega(\sum \deg^2)$$$ (which could be $$$\Omega(nm)$$$ worst case) for counting $$$C_3$$$ and $$$C_4$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh, I'm sorry. You're probably right. Then you might want to remove the hash table since it's not very efficient.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it +10 Vote: I do not like it

          Just store the indices (such as changing the vector to vector<pair<int, int> >) while storing the endpoints owo

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's amazing! Thank you so much for help!!