Chi's blog

By Chi, history, 6 months 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

»
6 months 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.

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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?

»
6 months 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)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. Im going to kill myself now

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Are you alive Chi?

      • »
        »
        »
        »
        4 weeks 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