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

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

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
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
← 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.

→ Ответить
»
8 лет назад, скрыть # |
 
Проголосовать: нравится +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)

→ Ответить