|
|
Uncompressed interval tree, and long longs everywhere -> AC with > 1,9 sec :) It is the last place now :) The problem is just working with arrays, the most difficult part is sorting, the rest is O(N) - why TL is 2 sec., especially given that there are more time-intensive problems with TL 0.5 sec.??? My very inefficient solution with long long's got AC in 0.125 sec, so 1 sec. here is more than enough... As you can see, your "very inefficient solution" is the best solution now. :) By the way, current best Java solution works 0.625 sec. Hm, really funny =) Interesting to know, what algo did other guys use...
And what's bottleneck for Java solutions? Input, or something else?
As for my question - still, as you can see, currently only one solution for this problem has runtime more than 1 sec., and in problem 1827, for instance, almost half of the solutions got TL, and I think many of them have runtime bit more than 1 sec. I just wanted to say that timelimit policy should be consistent - if you impose quite strict timelimits for other problems, it is quite strange to give more here... I can not understand it. Each routing table defines what gateway to use for every possible address (or that there is no gateway for some addresses). Hence, both routing tables from the input are mappings from addresses to gateways. The problem is to check equivalence of these mappings. |
|
|
