fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5. int main() {
  6. 	int n,e;
  7. 	cin>>n>>e;
  8. 	vector<int> g[n+1];
  9. 	vector<int> val(n+1);
  10. 	for(int i=1;i<=n;i++){
  11. 		cin>>val[i];
  12.  
  13. 	}
  14.  
  15. 	for(int i=1;i<=e;i++){
  16. 		int u;
  17. 		int v;
  18. 		cin>>u>>v;
  19.  
  20. 		g[u].push_back(v);
  21. 		g[v].push_back(u);
  22. 	}
  23.  
  24. 	int s;
  25. 	cin>>s;
  26. 	queue<int> q;
  27. 	q.push(s);
  28. 	vector<int> level(n+1,-1);
  29. 	level[s]=0;
  30.  
  31. 	vector<int> visited(n+1,0);
  32. 	vector<int> shortest(n+1,0);
  33. 	vector<int> cnt(n+1,0);
  34. 	vector<int> five_count(n+1,0);
  35.  
  36. 	visited[s]=1;
  37. 	shortest[s]=0;
  38. 	cnt[s]=1;
  39.  
  40. 	if(val[s]==5){
  41. 		five_count[s]=1;
  42. 	}
  43.  
  44. 	while(!q.empty()){
  45.        int a = q.front();
  46.  
  47. 	   q.pop();
  48.  
  49. 	   for(auto it : g[a]){
  50.            if(!visited[it]){
  51. 			q.push(it);
  52. 			visited[it]=1;
  53. 			shortest[it] = shortest[a]+1;
  54. 			if(val[it]==5){
  55. 				five_count[it] = five_count[a] + 1;
  56. 			}
  57. 			else{
  58. 					five_count[it] = five_count[a];
  59. 			}
  60.  
  61. 			cnt[it] = cnt[a];
  62.  
  63. 		   }
  64. 		   else{
  65. 		   	if(shortest[it]==shortest[a]+1){
  66. 		   		if(val[it]==5){
  67. 		   			if(five_count[a]+1>five_count[it]){
  68. 		   				five_count[it] = five_count[a]+1;
  69. 		   				cnt[it]=cnt[a];
  70.  
  71. 		   			}
  72. 		   			else if(five_count[a]+1==five_count[it]){
  73.  
  74. 		   				cnt[it]=cnt[a]+cnt[it];
  75.  
  76. 		   			}
  77. 		   		}else{
  78.  
  79. 		   			if(five_count[a]>five_count[it]){
  80. 		   				five_count[it] = five_count[a];
  81. 		   				cnt[it]=cnt[a];
  82.  
  83. 		   			}
  84. 		   			else if(five_count[a]==five_count[it]){
  85.  
  86. 		   				cnt[it]=cnt[a]+cnt[it];
  87.  
  88. 		   			}
  89. 		   		}
  90. 		   	}
  91. 		   }
  92. 	   }
  93. 	}
  94.  
  95. 	for(int i=1;i<=n;i++){
  96. 		if (visited[i] == 0) {
  97.             cout << -1 << " " << -1 << "\n"; 
  98.         } else {
  99.             cout << cnt[i] << " " << five_count[i] << "\n"; 
  100.         }
  101.  
  102.  
  103. 	}
  104. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
8 8 
0 5 5 0 0 5 5 5 
1 2
2 3 
3 4 
4 5 
1 6
6 7
7 8 
8 5 
1
stdout
copy 
1 0
1 1
1 2
1 2
1 3
1 1
1 2
1 3
https://ideone.com/Ktl6bB
language:
C++14 (gcc 8.3)
created:
2 days 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!