fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <cstring>
  21. #include <string>
  22.  
  23. using namespace std;
  24.  
  25. int M, N, X;
  26. #define FOR(i, N) for(int i = 0; i < N; i++)
  27. #define FOR1e(i, N) for(int i = 1; i <= N; i++)
  28. #define REP(i, X, N) for(int i = X; i < N; i++)
  29. #define REP1e(i, X, N) for(int i = X; i <= N; i++)
  30. #define SCAN(N) scanf("%d", &N)
  31. #define SCAN_2(N, X) scanf("%d %d", &N, &X)
  32. #define PAIR pair <string, int>
  33. #define ITR map <PAIR, vector <PAIR > >::iterator
  34. #define MP make_pair
  35. #define PP push_back
  36.  
  37. bool Vis[5010];
  38. map <PAIR, vector <PAIR > > AdjList;
  39.  
  40. #define All(it, AdjList) for(ITR it = AdjList.begin(); it != AdjList.end(); it++)
  41.  
  42. int BFS(PAIR s, string d){
  43. 	queue <PAIR> q; q.push(s);
  44. 	PAIR cur = s; Vis[0] = 1;
  45. 	int sz = 1, Cnt = 1;
  46. 	while(q.size()){
  47. 		while(sz--){
  48. 			cur = q.front(); q.pop();
  49. 			FOR(i, AdjList[cur].size()){
  50. 				PAIR child = AdjList[cur][i];
  51. 				if(child.first == d) 
  52. 					return Cnt;
  53. 				if(!Vis[child.second]){
  54. 					Vis[child.second] = 1;
  55. 					q.push(child);
  56. 				}
  57. 			}
  58. 		}
  59. 		sz = q.size(); Cnt++;
  60. 	}
  61. 	return 0;
  62. }
  63.  
  64. int main(){
  65. //	freopen("in.txt", "r", stdin);
  66. 	int T; SCAN(T);
  67. 	while(T--){
  68. 		AdjList.clear(); AdjList[MP("Erdos, P.", 0)].clear();
  69. 		SCAN_2(M, N); cin.ignore();
  70. 		int index = 1;
  71. 		while(M--){
  72. 			string Line; getline(cin, Line);
  73. 			stringstream SS(Line);
  74. 			vector <string> Words, Nodes;
  75. 			int i = 0;
  76. 			bool End = 0;
  77. 			for(string x; SS >> x; i++){
  78. 				Words.push_back(x);
  79. 				if(i%2){
  80. 					if(Words[i][Words[i].size()-1] == ':') End = 1;
  81. 					Words[i].erase(Words[i].size()-1, 1);
  82. 					Words[i-1] += ' '+Words[i];
  83. 					Nodes.push_back(Words[i-1]);
  84. 					if(End) break;
  85. 				}
  86. 			}
  87. 			FOR(i, Nodes.size()-1)
  88. 				REP(j, i+1, Nodes.size()){
  89. 					bool F = 0;
  90. 					PAIR x(MP(Nodes[i], i)), y(MP(Nodes[j], j));
  91. 					All(it, AdjList){
  92. 						if(it->first.first == x.first)
  93. 						{x.second = it->first.second; F = 1; break;}
  94. 					}
  95. //					(F) ? F = 0 : x.second == index++;
  96. 					if(F) F = 0; else x.second = index, index++;
  97. 					All(it, AdjList){
  98. 						if(it->first.first == y.first)
  99. 						{y.second = it->first.second; F = 1; break;}
  100. 					}
  101. 					if(F) F = 0; else y.second = index, index++;
  102. 					AdjList[x].push_back(y); AdjList[y].push_back(x); 
  103. 			}
  104. 		}
  105. 		while(N--){
  106. 			memset(Vis, 0, AdjList.size()+5);
  107. 			string Name; getline(cin, Name);
  108. 			if(Name == "Erdos, P.") {puts("Erdos, P. 0"); continue;}
  109. 			else{
  110. 				int Num = BFS(MP("Erdos, P.", 0), Name);
  111. 				(Num) ? printf("%s %d\n", Name.c_str(), Num) : printf("%s infinity\n", Name.c_str());
  112. 			}
  113. 		}
  114. 	}
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
1
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices 
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
stdout
copy 
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
https://ideone.com/KsnVd0
language:
C++ (gcc 8.3)
created:
10 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!