### once_twice's blog

By once_twice, history, 8 days ago, ,

Can someone help me in finding why my code TLE's for some cases.

• +6

 » 8 days ago, # |   +2 I would suggest dijkstra.To take care for the coupon we need to maintain two best values per city, one without having used the coupon, one with having used it.We would use a priority_queue else TLE since it is to much state changes. It took me some tries to find a configuration where it is AC. Not sure if this is hackable.I assume it would work if you use a priority_queue in function dick(). Code#include using namespace std; const bool ready = [](){ ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(12); return true; }(); const double PI = acos(-1); using ll= long long; #define int ll #define fori(n) for(int i=0; i>i; #define cins(s) string s; cin>>s; #define cind(d) double d; cin>>d; #define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; } #define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; } #define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; } using pii= pair; using pdd= pair; using vd= vector; using vb= vector; using vi= vector; using vvi= vector; using vs= vector; const int INF=4e18; void solve() { cini(n); cini(m); vector> adj(n); for(int i=0; i q; q.emplace(0,0); while(q.size() && -q.top().firstdp[0][node]+chl.second) { dp[0][chl.first]=dp[0][node]+chl.second; pu=true; } if(dp[1][chl.first]>dp[1][node]+chl.second) { dp[1][chl.first]=dp[1][node]+chl.second; pu=true; } if(dp[1][chl.first]>dp[0][node]+(chl.second/2)) { dp[1][chl.first]=dp[0][node]+(chl.second/2); pu=true; } if(pu) q.emplace(-dp[1][chl.first], chl.first); } } cout<
•  » » 8 days ago, # ^ |   0 Can u please tell why priority queue has a better time complexity than a set? Even for question in SPOJ i saw people cursing set.
•  » » » 8 days ago, # ^ |   0 The time complexity of set and priority_queue are same, they both should work. Problems arise by using a simple queue without sorting.In fact, if memory size matters, we can use an additional set to make sure every vertex is at most once added to the priority_queue. This limits the size of the queue to max the number of vertex.
•  » » » » 8 days ago, # ^ |   0 Then we can always use a set for that matter?
•  » » » » » 8 days ago, # ^ |   0 priority_queue and set have the same time complexity, but still set is somewhat slower.
•  » » 8 days ago, # ^ |   0 I am using priority_queue only in dick()
•  » » » 8 days ago, # ^ |   0 Ok, I didn't recognize that.
 » 8 days ago, # |   0
•  » » 8 days ago, # ^ |   0 English description please
•  » » » 8 days ago, # ^ |   0 deep breatha
 » 8 days ago, # |   +4 I've solved the same problem recently with coincidentally the same idea as your's, here's my AC submission. https://paste.ubuntu.com/p/cKqC9Gfv6S/
•  » » 8 days ago, # ^ |   0 Yea i get the idea , but what is wrong with my implementation. Why does it TLE. It's really frustrating
•  » » » 8 days ago, # ^ |   +3 You put the vertex to pair.first, and dist to pair.second, so the queue sorts the entries by vertex number instead of distance.pq.push({to,dist[to]});
•  » » » » 8 days ago, # ^ |   0 Oh fuck you are right. Thanks bro
•  » » » » 8 days ago, # ^ |   0 Accepted , thanks a lot dude
•  » » 7 days ago, # ^ |   0 nice code can you tell me what is the significance of prev in your code you don't seem to use it anywhere also what i guess is that you were trying to track the path using prev and making the maximum of flight cost in your path to halve right? can you tell me why it won't work?
•  » » » 7 days ago, # ^ |   0 So I was trying to make a greedy before. That take smallest cost path and then discount max element in that path. But that failed. So then I did dijkstra
•  » » » 6 days ago, # ^ |   0 prev has no use in that question, I was doing CSES problems in a sequence and one question before that wanted you to find shortest path nodes so for that I used prev. I've made all my CSES submissions public to github if you want to checkout that question refer: https://codeforces.com/blog/entry/77863