Show all threads Hide all threads Show all messages Hide all messages | Still WA #11 ? | Hikmat Ahmedov | 1930. Ivan's Car | 16 Aug 2023 16:30 | 4 | This test helped me to find my bug. I modified dijkstra algo and added direction array. 9 12 7 3 9 3 9 2 1 2 1 3 4 7 4 1 5 1 4 8 5 8 6 5 2 6 1 8 Answer:0 Edited by author 31.01.2013 17:37 Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome You have to use 2d array to have 2 min costs from s to t with 2 states 0 (up) and 1 (down) (dis[u][0], dis[u][1]), if you just you 1d array and AC, it must be lucky. This is my AC code run in 0.031s: ((const) inf = 1e9, (define) ep = emplace (= push/insert), (define) eb = emplace_back (= push_back), ep and eb both are faster than push and push_back, emplace_front/emplace/emplace_back = push_front/(push/insert)/push_back but faster because it doesn't copy then moves value into array, it pushes directly into array)
#pragma GCC optimize( "Ofast" ) #pragma GCC target( "avx2", "sse4.2", "abm", "bmi", "bmi2", "fma", "mmx", "popcnt", "lzcnt" ) #include <bits/stdc++.h> #define endl '\n' #define inf 1e18 #define int long long #define pii pair <int, int> #define vii vector <pii> #define tiii tuple <int, int, int> #define viii vector <tiii> #define ep emplace #define eb emplace_back using namespace std; const int MaxN = 1e4 + 10; int n, m, s, t, f[MaxN][2]; vii a[MaxN]; priority_queue <tiii, viii, greater <tiii>> pq; signed main() { cin.tie(0) -> sync_with_stdio(0); __builtin_ia32_ldmxcsr ( 40896 );
fill(&f[0][0], &f[0][0] + sizeof(f) / sizeof(f[0][0]), inf);
cin >> n >> m; for (int u, v, i = 1; i <= m; ++i) { cin >> u >> v; a[u].eb(v, 0); a[v].eb(u, 1); } cin >> s >> t;
f[s][0] = f[s][1] = 0; pq.ep(f[s][0], s, 0); pq.ep(f[s][1], s, 1); while (!pq.empty()) { auto [x, u, y] = pq.top(); pq.pop(); if (x > f[u][y]) continue; if (u == t) break; for (auto [v, z] : a[u]) { int w = f[u][y] + (y != z); if (f[v][z] > w) pq.ep(f[v][z] = w, v, z); } }
cout << min(f[t][0], f[t][1]) << endl; } if you have any question, you can ask me :)) | I will just post the soution because i want to ruin it for you ;) | Ishan Pandey | 1930. Ivan's Car | 28 Mar 2023 23:19 | 3 | #include<bits/stdc++.h> using namespace std; #define endl "\n" #define int long long #define mod 1000000007 #define maxn 10010 #define pb push_back #define mp make_pair #define fi first #define se second #define inf 100000000000 vector<pair<int, int>> adj[maxn]; int n, m; // struct node //for edges // { // int pos, dir, dist; // node(){}; // node(int _pos, int _dir) // { // pos = _pos; // dir = _dir; // } // }; int go(int s, int e) {
int dist[maxn][2]; for(int i=0; i<maxn; i++) { for(int j=0; j<=1; j++) { dist[i][j] = inf; } } deque<pair<int, int>> q; //pair->{node, edgedir} //making direction list here, q.push_back({s, 0}); //0->outgoing to node s dist[s][0] = 0; q.push_back({s, 1}); //1->incoming from node s dist[s][1] = 0; while(!q.empty()) { pair<int, int> cur = q.front(); //node int v = cur.first; int dir = cur.second; //dist int dv = dist[v][dir]; //guarenteed that shortest dist till cur node has been calc already q.pop_front(); //if(dv == inf) break;
if(cur.first == e) return dv; //gauarenteed via djikstra that this willbe minimest
//relax all the neighbours, and as you relax one , push into minheap the nodes for(auto it: adj[v]) { int to = it.fi; int dir2 = it.se; //previous //note that for type edge dir, you have relax for all neighbouring nodes int dist2=0; if(dir2 == dir) { dist2 = dist[v][dir2]; //dist[to][dir2] = min( dist[to][dir2], dist[v][dir2] ); } else dist2 = dist[v][dir] + 1; // dist[to][dir2] = min( dist[to][dir2], dist[v][dir] + 1);
//only relax and add to queue, if less than prev distance to this node if(dist2 < dist[to][dir2]) { if(dist2 <= dv) //less than equal to cur_dist q.push_front({to, dir2}); else q.push_back({to, dir2});
dist[to][dir2] = dist2;
}
} } return -1; } void solve() { cin>>n>>m; for(int i=1;i<=m;i++) { int x, y; cin>>x>>y; adj[x].pb({y, 0}); adj[y].pb({x, 1}); } int s, e; cin>>s>>e; //cout<<"hi"; int ans = go(s, e); cout<<ans<<endl; } signed main() { int t=1; //cin>>t; while(t--) { solve(); } return 0; } I do not understand the final push back and front part. Why to push only if dist is less than dv? Why are we comparing it to dv? If it is for the right position in the queue of the pushed element(like in 0-1 bfs),then how do we know that the queue only has 0-1? That is the underlying part of the 0-1 bfs right?else it is dijkstra. I think the queue has difference of 1 between its min and max. Can you tell what all is true and exactly what is happening. I would really appreciate. Thank you Edited by author 04.05.2020 20:46 Edited by author 04.05.2020 20:47 if(dist2 <= dv) //less than equal to cur_dist q.push_front({to, dir2}); else q.push_back({to, dir2}); CAN YOU EXPLAIN ME THIS PART WHY DIST 2 GREATER IS PUSHED BACK NOT IN FRONT AND VICE VERSA WHAT I MEAN TO KNOW IS WHY WE COMPARE CONNECTED VERTEX DISTANCE | Easy 0-1 bfs with deque | 👾_challenger128_[PermSU] | 1930. Ivan's Car | 23 Feb 2021 19:48 | 1 | | What is test 5? | mr.erfan | 1930. Ivan's Car | 31 Jul 2020 21:05 | 1 | please help me. i have some problems in test 5. please help me! | Test for WA5 | Vladimir Plyashkun [USU] | 1930. Ivan's Car | 24 Jul 2020 17:15 | 2 | try this: 3 2 1 3 2 3 1 2 answear: 1 You realy snooze a lot my code have wrong in test5 and the ansear this test is correct:( Please do not waste the rest of your time Edited by author 25.07.2020 15:37 Edited by author 25.07.2020 15:37 | No subject | Yuzhen | 1930. Ivan's Car | 22 Jul 2020 05:25 | 1 | can someone please provide test #6? | My mistake for WA #6 | ajay jadhav | 1930. Ivan's Car | 8 May 2020 20:33 | 1 | I had maintained dis[n+1][2] for distance. But visited array was vis[n+1], changed it to vis[n+1][2] and simple bfs. | quite a tricky ques | luffy | 1930. Ivan's Car | 11 Feb 2020 23:40 | 1 | Easy concept, just to think for a while. AC in one go! | easy problem | bhaskar bhardwaj | 1930. Ivan's Car | 10 Feb 2020 23:55 | 1 | just use bfs as a modified version of dijkstra and you will be done | Hint | ... | 1930. Ivan's Car | 12 Jul 2017 17:22 | 2 | Hint ... 1 Dec 2016 15:08 0-1 bfs on graph with 2 * n verticles. Re: Hint ComebackSeason 12 Jul 2017 17:22 Used this idea, but instead I used another adj. list to store directions cin >> u >> v graph[u].push_back(v); direction[u].push_back(0); graph[v].push_back(u); direction[v].push_back(1); 0.046s AC Edited by author 12.07.2017 17:23 | Any Idea about WA #5 | Apptica | 1930. Ivan's Car | 16 Jul 2016 11:34 | 1 | I am using dijkstra by adding a reverse edge of weight 1. Answer will be MIN ( Shortest distance, total_edges - shortest_distance); | If you're using BFS :D | GastonFontenla | 1930. Ivan's Car | 2 Aug 2015 15:05 | 1 | If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion. | sample test case 2??how is it possible | ayush vatsa | 1930. Ivan's Car | 26 Jul 2015 16:19 | 2 | 3 3 1 2 2 3 3 1 1 3 how is this possible? from 1 to 2 there is an uphill road...from 2 to 3 there is also an uphill road...then how can there be a uphill road from 3 to 1??from 3 to 1 there should be a downhill road... correct me if i am wrong.. Don't worry about that, it's just an example and the contraints don't say nothing about. | If you have WA #12 . Try this test. | Adhambek C# | 1930. Ivan's Car | 3 Jan 2015 15:16 | 4 | 6 6 4 2 1 2 4 5 2 3 2 6 6 4 1 5 answer : 0 Edited by author 07.01.2014 01:25 ? 6 6 4 2 1 2 4 5 2 3 2 6 6 4 1 5 answer : 0 Edited by author 07.01.2014 01:25 are you sure? isn't the answer is 2 the optimal route is: 1 -> 2 -> 6 -> 4 -> 5 and requires no gear changes Of course . it is right answer | Problem with time | Narek X | 1930. Ivan's Car | 13 Aug 2014 22:31 | 4 | In this problem I use bfs and Dejikstra, in two cases I got AC, but my solutions are very slowly then others. I can't understand way ? How fast your Dijkstra's algorithm? The best program that I can write run in time 0.171s, but other users solv it in 0.031. My solution with Dijkstra work 0.312s :) | Just good test | [RISE] Levon Oganesyan [RAU] | 1930. Ivan's Car | 5 Aug 2014 16:27 | 1 | 9 15 1 2 3 1 1 5 4 2 6 2 3 4 3 6 4 5 6 5 5 7 6 7 6 8 8 7 7 9 8 9 1 9 Ans: 0 | About using BFS | skrcode | 1930. Ivan's Car | 27 Jun 2014 01:14 | 1 | BFS solution gets accepted.. but it fails in many cases. However the perfect solution to be used is Dijkstra's. The test cases do not contain cases where cycles terminate at nodes in between source and destination. | WA 6 | Mamuka Sakhelashvili [Freeuni] | 1930. Ivan's Car | 9 Feb 2014 04:05 | 1 | WA 6 Mamuka Sakhelashvili [Freeuni] 9 Feb 2014 04:05 Could you tell me some useful test, if you had the same problem?! Thanks ^_^ | WA12,,, please give me test... | Hoderu | 1930. Ivan's Car | 17 Nov 2013 23:44 | 1 | I use BFS, but WA12 :( Help me, pleas give me test | is it correct test? | Uzbek boy | 1930. Ivan's Car | 21 Jul 2013 02:29 | 2 | Nope, And I quote "There is at most one road between any two cities". |
|
|