ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1886. Trip 2

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.

Edited by author 30.03.2012 22:05
Re: help wa 17 (Admin! test is weak!)
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
:)