my simple dp solution got tle 17. after optimizing with bin_search and map (for searching if a range of edges already visited) but surprisingly this got me wa 17. please, help. some useful test cases or hint would be really appreciated.
Thanks in advance :)


Edited by author 30.03.2012 22:05

got AC but shouldn't have. i used map to keep mark upto what edges outgoing from a certain node we have already dp'ed. and return in log(n). but when i have to dp more then dp'ed and entered into map for that node. however, this gave wa 17. then i dp'ed some more node although already dp'ed. if this 'some more' is less than 9 then i get wa on (18~23) tests. but when it is >=9 i get AC. i dunno why my soln was WA, it seemed perfect. but even more surprising when i get AC like this. Portion of my code:-

#define WHATTHEHECK 9
...

map<int,double> optimize[MAX];
...

int lim1=arr[edgeno].dtime+arr[edgeno].dur,lim2=lim1+arr[edgeno].delay;
    int s1=v[to].size(),s2=s1;
    int lo=0,hi=s1-1,mid;
    while(lo<=hi){
        mid=(lo+hi)/2;
        if(lim1<=arr[v[to][mid]].dtime){
            hi=mid-1,s1=mid;
        }else lo=mid+1;
    }
    lo=0,hi=s2-1;
    while(lo<=hi){
        mid=(lo+hi)/2;
        if(lim2<=arr[v[to][mid]].dtime){
            hi=mid-1,s2=mid;
        }else lo=mid+1;
    }
    int i=-1;
    if(optimize[to].size()==0) i=v[to].size()-1;
    else i=min((*optimize[to].begin()).first+WHATTHEHECK,v[to].size()-1);
    if(i>=s1){
        for(;i>=s1;--i){
            optimize[to][i]=ret1=min(ret1,dp(v[to][i]));
        }
    }
    if(s1<v[to].size()) ret1=optimize[to][s1];
    if(s2<v[to].size()) ret2=optimize[to][s2];

ps: i would be really glad if someone explain me what i did wrong and what's going on here
:)

I got WA17 when I wrongly (overwrite old mean) insert into segment tree flights with same departure airport and same departure time.