luka25's blog

Why TLE
By luka25, history, 9 years ago, In English

I've written the solution for 543 B,I think it works fine but gets time limit on test 8.I ckecked and it doesn't pass inputing phase.How can it happen with 3000 numbers?

My submission

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Use faster I/O. You can either use ios_base::sync_with_stdio(0);cin.tie(0); at the beginning of your program and continue using cin/cout or use scanf/printf.

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

    will it help on 3000 numbers?

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

      If the problem with your code is not the algorithm, it should make a significant difference. Input with these techniques can be more than 5 times faster.

      → Reply
»
9 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

special for you fixed code .

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    research BFS implementation. for example

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

    thanks very much,so was the problem in implementation of bfs?when i checked it failed during imputing and didn't even reach bfs part

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

i didn't consider map is logN just changing to unordered_map fixed it.

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

    Your code awesome beautiful!!! Are you understand why std::map — TLE, std::unordered_set — AC ??

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

      I used map instead of array because it can be cleared more easily, didn't think of it being too slow.

      → Reply
      • »
        »
        »
        »
        9 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it 
        std::map<int> mp;
......
mp.clear(); // seems more easily, actually it very-very heave operation - it destroyed many of memory.


//--------------------------
bool visited[1<<17];

....
memset(visited, 0, sizeof(visited)); // actually very cheap operation than std::map<>::clear.
        → Reply