Show all threads Hide all threads Show all messages Hide all messages 
Easy 01 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. 
Still WA #11 ?  Hikmat Ahmedov  1930. Ivan's Car  5 May 2020 22:28  3 
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 
I will just post the soution because i want to ruin it for you ;)  Ishan Pandey  1930. Ivan's Car  4 May 2020 20:39  2 
#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 01 bfs),then how do we know that the queue only has 01? That is the underlying part of the 01 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 
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 01 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". 