fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17.  
  18. vector<vector<int>> graph;
  19. vector<int> nodes;
  20.  
  21. void consistency(int n, int m){
  22.  
  23.  
  24. 	queue<int> q;
  25. 	q.push(1);
  26. 	vector<int> visited(n+1, false);
  27. 	vector<int> levels(n+1, 0);
  28. 	vector<int> maxFives(n+1, 0);
  29. 	visited[1] = true;
  30. 	if(nodes[1] == 5) maxFives[1] = 1;
  31.  
  32. 	vector<int> dp(n+1, 0);
  33. 	dp[1] = 1;
  34.  
  35.  
  36. 	while(!q.empty()){
  37. 		auto v = q.front(); q.pop();
  38.  
  39. 		for(int u : graph[v]){
  40. 			if(u == v) continue;
  41. 			if(visited[u]){
  42. 				if(levels[v]+1 == levels[u]){
  43. 					int extra = nodes[u] == 5 ? 1 : 0;
  44. 					int maxSoFar = maxFives[v] + extra;
  45.  
  46. 					if(maxSoFar > maxFives[u]){
  47. 						maxFives[u] = maxSoFar;
  48. 						dp[u] = dp[v];
  49. 					}
  50. 					else if(maxSoFar == maxFives[u]){
  51. 						dp[u] += dp[v];
  52. 					}
  53. 				}
  54. 			}
  55. 			else{
  56. 				q.push(u);
  57. 				visited[u] = true;
  58. 				levels[u] = levels[v]+1;
  59.  
  60.  
  61. 				int extra = nodes[u] == 5 ? 1 : 0;
  62. 				maxFives[u] = maxFives[v] + extra;
  63.  
  64. 				int maxSoFar = maxFives[v] + extra;
  65. 				if(maxSoFar == maxFives[u]) dp[u] += dp[v];
  66. 			}
  67.  
  68. 		}
  69. 	}
  70.  
  71.  
  72.  
  73. 	for(int i=1; i<=n; i++){
  74. 		cout << i << "->" << dp[i] << "," << maxFives[i] << endl;
  75. 	}
  76.  
  77.  
  78. }
  79.  
  80.  
  81.  
  82. void solve() {
  83.  
  84. 	int n, m;
  85. 	cin >> n >> m;
  86.  
  87. 	graph.resize(n+1); // 1 based indexing
  88. 	nodes.resize(n+1);
  89.  
  90. 	for(int i=1; i<=n; i++) cin >> nodes[i]; // 1 index based
  91. 	for(int i=0; i<m; i++){
  92. 		int x, y;
  93. 		cin >> x >> y;
  94. 		graph[x].push_back(y);
  95. 		graph[y].push_back(x);
  96. 	}
  97.  
  98. 	consistency(n, m);
  99.  
  100.  
  101. }
  102.  
  103.  
  104.  
  105.  
  106.  
  107. int32_t main() {
  108.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.  
  110.     int t = 1;
  111.     while (t--) {
  112.         solve();
  113.     }
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 6
0 5 5 5 0 0
1 2
1 3
2 4
3 5
4 6
5 6
stdout
copy 
1->1,0
2->1,1
3->1,1
4->1,2
5->1,1
6->1,2
https://ideone.com/iXzCvW
language:
C++14 (gcc 8.3)
created:
8 hours 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!