Tom--CCS's blog

"Mysterious" low running speed in Java
By Tom--CCS, history, 6 years ago, In English

Recently in Educational Codeforces round 46 I wrote the following programme for 1000E - Нужно больше боссов in Java:

39737014

Now I am pretty sure that the program runs in O(n + m) time(it is a dfs plus an iteration over the edges). However, the program got rejected due to Time Limit Exceeded despite its optimal asymptotic efficiency. Would anyone point out which part of my programme is consuming lots of time? I am a newbie in programming and really appreciate any help!

Update: Thank you all for giving me advice! I have solved the problem.

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

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

Use faster input routines due to massive input (~10^6 integers).

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

Scanner is too slow in Java for competitive programming problems, replace it with a buffered reader, or use a custom written scanner.

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

Slow I/O

I just copied Petr's Java template and it passed.

→ Reply
»
6 years ago, # |
  Vote: I like it -36 Vote: I do not like it

switch to C++

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

Auto comment: topic has been updated by Tom--CCS (previous revision, new revision, compare).

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

LoOoOOL. The fact that you survived for so long and even became purple while using Scanner in Java is more mysterious than the running speed of Java itself.

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

    Now he has fast Scanner and he became orange

    → Reply