Блог пользователя Chi

Help with TLE verdict
Автор Chi, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    Keep it up.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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)

→ Ответить