fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define taskname "cross"
  3. using namespace std;
  4. const int lim = 5e4 + 5;
  5. int n, m, d[lim];
  6. vector<int>g[lim];
  7. namespace sub13{
  8. 	void solve(){
  9. 		vector<int>ans, f(n + 1);
  10. 		for(int i = 1; i <= n; i++){
  11. 			fill(f.begin(), f.end(), -1);
  12. 			f[i] = 0;
  13. 			queue<int>q;
  14. 			q.push(i);
  15. 			while(!q.empty()){
  16. 				int u = q.front();
  17. 				q.pop();
  18. 				for(int& v : g[u]){
  19. 					if(f[v] == -1){
  20. 						f[v] = f[u] + 1;
  21. 						q.push(v);
  22. 					}
  23. 				}
  24. 			}
  25. 			ans.push_back(i);
  26. 			for(int j = 1; j <= n; j++){
  27. 				if(d[j] != -1 && d[j] != f[j]){
  28. 					ans.pop_back();
  29. 					break;
  30. 				}
  31. 			}
  32. 		}
  33. 		cout << ans.size() << "\n";
  34. 		for(int& i : ans){
  35. 			cout << i << " ";
  36. 		}
  37. 	}
  38. }
  39. namespace sub2{
  40. 	void solve(){
  41. 		if(d[1] == -1){
  42. 			cout << n << "\n";
  43. 			for(int i = 1; i <= n; i++){
  44. 				cout << i << " ";
  45. 			}
  46. 			return;
  47. 		}
  48. 		vector<int>f(n + 1, -1);
  49. 		f[1] = 0;
  50. 		queue<int>q;
  51. 		q.push(1);
  52. 		while(!q.empty()){
  53. 			int u = q.front();
  54. 			q.pop();
  55. 			for(int& v : g[u]){
  56. 				if(f[v] == -1){
  57. 					f[v] = f[u] + 1;
  58. 					q.push(v);
  59. 				}
  60. 			}
  61. 		}
  62. 		vector<int>ans;
  63. 		for(int i = 1; i <= n; i++){
  64. 			if(f[i] == d[1]){
  65. 				ans.push_back(i);
  66. 			}
  67. 		}
  68. 		cout << ans.size() << "\n";
  69. 		for(int& i : ans){
  70. 			cout << i << " ";
  71. 		}
  72. 	}
  73. }
  74. namespace sub4{
  75. 	bitset<lim>cnt[lim];
  76. 	vector<int>ans;
  77. 	int f[lim];
  78. 	vector<int>ver[lim];
  79. 	void solve(){
  80. 		memset(f, -1, sizeof(f));
  81. 		int sd = 0;
  82. 		for(int i = 1; i <= n; i++){
  83. 			cnt[i].reset();
  84. 			if(d[i] != -1){
  85. 				ver[f[i] = d[i]].push_back(i);
  86. 				cnt[i][i] = true;
  87. 				sd++;
  88. 			}
  89. 		}
  90. 		if(sd == 0){
  91. 			cout << n << "\n";
  92. 			for(int i = 1; i <= n; i++){
  93. 				cout << i << " ";
  94. 			}
  95. 			return;
  96. 		}
  97. 		for(int i = n; i > 0; i--){
  98. 			for(int& u : ver[i]){
  99. 				for(int& v : g[u]){
  100. 					if(f[v] == -1){
  101. 						ver[f[v] = f[u] - 1].push_back(v);		
  102. 					}
  103. 				}
  104. 			}
  105. 			for(int& u : ver[i]){
  106. 				for(int& v : g[u]){
  107. 					if(f[v] == f[u] - 1){
  108. 						cnt[v] |= cnt[u];
  109. 					}
  110. 				}
  111. 			}
  112. 		}
  113. 		vector<int>ans;
  114. 		for(int& i : ver[0]){
  115. 			if(cnt[i].count() == sd){
  116. 				ans.push_back(i);
  117. 			}
  118. 		}
  119. 		cout << ans.size() << "\n";
  120. 		sort(ans.begin(), ans.end());
  121. 		for(int& i : ans){
  122. 			cout << i << " ";
  123. 		}
  124. 	}
  125. }
  126. int main(){
  127. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  128. 	if(fopen(taskname".inp", "r")){
  129. 		freopen(taskname".inp", "r", stdin);
  130. 		freopen(taskname".out", "w", stdout);
  131. 	}
  132. 	cin >> n >> m;
  133. 	for(int i = 0; i < m; i++){
  134. 		int u, v;
  135. 		cin >> u >> v;
  136. 		g[u].push_back(v);
  137. 		g[v].push_back(u);
  138. 	}
  139. 	for(int i = 1; i <= n; i++){
  140. 		cin >> d[i];
  141. 	}
  142. 	if(max(n, m) <= 5000){
  143. 		sub13::solve();
  144. 	}
  145. 	else if(*max_element(d + 2, d + n + 1) == -1){
  146. 		sub2::solve();
  147. 	}
  148. 	else{
  149. 		sub4::solve();
  150. 	}
  151. }
Success #stdin #stdout 0.01s 7952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aL1ZJ4
language:
C++14 (gcc 8.3)
created:
1 day 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!