### t0nyukuk's blog

By t0nyukuk, 10 years ago,

• +3

 » 10 years ago, # | ← Rev. 2 →   +4 It looks like a usual dp on a tree. I think you should write a comparator, like 'What vertex we should go into?'. Then run DFS, and at each step sort all children of the current vertex by this comparator and visit them in this exact order. Once you visit a subtree, it becomes a vertex with its own parameters.I may be wrong, but it's the first solution I would think of.
•  » » 10 years ago, # ^ |   +3 i will write comparator but which priority? i have no idea
•  » » » 10 years ago, # ^ | ← Rev. 3 →   +3 Write the mathematical expression, what number of citizen will be dead if we go to the first city and then to the second. Then write the same expression if you visit the cities in the opposite order. Sign of the difference of these values will show which city of these two should be visited first.
•  » » » » 10 years ago, # ^ |   +3 i try this but i can't, i will try this once again
 » 10 years ago, # | ← Rev. 7 →   +2 my code is here and i dont know is it true solutiondefine fi firstdefine se seconddefine SIZE(A) ((int)A.size())define pb push_backusing namespace std;const int MAXN = 100010;typedef pair ii;vector way[MAXN];int n;long long vic[MAXN];struct node{ long long a,b,w,len; node(int _a=0,int _b=0,int _w=0,int _len=0){ a=_a;b=_b;w=_w;len=_len; } friend bool operator < (const node &a,const node &b){ return a.b*b.aw]){ res+=time*it->a+f(it->w)+it->len*it->a; time+=it->b; } return res; }int main(){ scanf(" %d",&n); for(int i=1;i<=n;i++) scanf(" %lld",&vic[i]); for(int i=1,a,b,c;i
•  » » 10 years ago, # ^ |   0 my bug is "set", it will be "multiset". thanks dalex
•  » » » 10 years ago, # ^ |   0 Use vectors + sorting next time, it should be a bit faster than sets with their red-black trees.
 » 10 years ago, # | ← Rev. 2 →   0 AppleZ the previous comment for my wrong idea. Thanks
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 Sorry...