At last got AC..
my algo is binary search on answer + dfs to check

in my code I had such fragment:
for (i = 0; i < n; i++)
{
    g[i].clear();
        color[i].clear();
    u[i] = -1;
}
and got TLE

then I changed clear() function to resize()
for (i = 0; i < n; i++)
{
    g[i].resize(0);
    color[i].resize(0);
    u[i] = -1;
}
and got AC in 0.2sec
can anybody explain what happend?
clear() works so slow???

I'm shocked as well!!! I don't know what place creators of STL wrote it through...

Tbilisi SU: Giorgi, Akaki, [Andrew], thank you for this trick!

What about such explanation?

clear() frees memory, and the next time memory should be allocated again.

resize() just changes internal pointer to the end of array nothing is freed and nothing is allocated then.

I think that 5x difference is because Timus compiler uses /O1 switch instead of usual /O2. In /O2 mode heap manager is very fast.

I think it works much slower than 5x . because , number of edges in graph is not more than 10000 , binary search runs log(5000) ~ 12 times . for example if clear() needs O(n) time to clear vector , where n is number of elements in it, then total number of operations is 2*10000*12 = 240000, it seems that it runs 500 times slower...


Edited by author 09.02.2009 14:25