fork(4) download
copy 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <ctime>
  8. #include <deque>
  9. #include <functional>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <list>
  13. #include <map>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <string>
  19. #include <vector>
  20.  
  21. using namespace std;
  22.  
  23. #define FOR(i, N) for(int i = 0; i < N; i++)
  24. #define FOR1e(i, N) for(int i = 1; i <= N; i++)
  25. #define REP(i, M, N) for(int i = M; i < N; i++)
  26. #define REPe(i, M, N) for(int i = M; i <= N; i++)
  27. #define sc(N) scanf("%d", &N)
  28. #define scsc(M, N) scanf("%d %d", &M, &N)
  29. #define scscsc(M, N, O) scanf("%d %d %d", &M, &N, &O)
  30. #define all(s) s.begin(), s.end()
  31. #define gt(s) getline(cin, s)
  32. #define ms(a, v) memset(a, v, sizeof a)
  33. #define mp make_pair
  34. #define pb push_back
  35. #define pq priority_queue
  36. #define ss stringstream
  37.  
  38. typedef long long ll;
  39. typedef pair<int, int> pii;
  40. typedef vector<int> vi;
  41.  
  42. const int oo = 1 << 30;
  43. const int MAX = 1e4 + 1;
  44. const int mod = 1e9 + 7;
  45.  
  46. int dr[] = { 0, -1, 0, 1 };
  47. int dc[] = { 1, 0, -1, 0 };
  48.  
  49. inline int Pow(int b, int p) { if (!p) return 1; int sq = Pow(b, p >> 1); sq *= sq; if (p & 1) sq *= b; return sq; }
  50. inline int gcd(int a, int b) { if (!a) return b; return gcd(b % a, a); }
  51. inline string toString(int x) { ss SS; SS << x; return SS.str(); }
  52.  
  53. vi adj[2 * MAX];
  54. bool vis[2 * MAX];
  55.  
  56. int bfs(int src, int des){
  57. 	if (src == des)
  58. 		return 0;
  59. 	queue <int> q; q.push(src);
  60. 	int cur = src, sz = 1;
  61. 	int moves = 1;
  62. 	while (q.size()){
  63. 		while (sz--){
  64. 			cur = q.front(); 
  65. 			q.pop();
  66. 			FOR(i, adj[cur].size()){
  67. 				int child = adj[cur][i];
  68. 				if (child == des)
  69. 					return moves;
  70. 				if (!vis[child]){
  71. 					vis[child] = 1;
  72. 					q.push(child);
  73. 				}
  74. 			}
  75. 		}
  76. 		moves++;
  77. 		sz = q.size();
  78. 	}
  79. 	return oo;
  80. }
  81.  
  82. void pre_processing(){
  83. 	FOR(i, 2 * MAX)
  84. 		adj[i].clear();
  85. 	ms(vis, 0);
  86. 	REP(i, 1, 2 * MAX){
  87. 		adj[i].push_back(2 * i);
  88. 		adj[i].push_back(i - 1);
  89. 	}
  90. }
  91.  
  92. int main(){
  93. #ifndef ONLINE_JUDGE
  94. 	freopen("in.txt", "r", stdin);
  95. #endif
  96. 	pre_processing();
  97. 	int n, m;
  98. 	while (cin >> n >> m){
  99. 		cout << bfs(n, m) << endl;
  100. 	}
  101. 	return 0;
  102. }
Success #stdin #stdout 0s 3748KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4zLqpn
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!