Chi's blog

Help with TLE verdict
By Chi, history, 5 years ago, In English

I tried solving problem 321C — Ciel the commander with centroid decomposition. I think thats what many people did and got an AC with, but my submission got a TLE. Could anyone tell me why did it exceed the time limit?

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

assuming your D&C algo is correct, you can try using edge list instead of adj list. That means just use a primitive array to store edges.

Also, dont use long long everywhere. just use it where necessary. It causes unnecessary computation.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Sometimes, just sometimes, you are more useful than those LooOoooOoOOooOoLoOoOoOOoOooOoOOLoOOoOoOoOoOooOoLs.

    Keep it up.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      LooOoOoOOoLoOoOoOooOooOoOooooLooOooooOOoOooOoooL. ROFL. LMAO.

      It depends on the kind of blog post that I am commenting on. If people making stupid blog posts, they deserve to get stupid comments. If they make a genuine effort to write a proper blog, then they'll deserve a proper reply. Fair enough?

      → Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Your if constraint in dfs function is incorrect.

Instead of if(adj[node][i]!=p&&!visited[node]), You can change it into if(adj[node][i]!=p&&!visited[adj[node][i]])

If the test case is star graph, then for each vertex your dfs will iterate M edges. So the complexity for dfs only is O(NM)

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

    Thank you. Im going to kill myself now

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Are you alive Chi?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        well thanks to those dumb avenging thingy guys i cant be dead anymore now

        → Reply