fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using ld = long double;
  7.  
  8. using vi = vector<int>;
  9. using vll = vector<ll>;
  10. using pii = pair<int, int>;
  11. using pll = pair<ll, ll>;
  12. using vipair  = vector<pair<ll, ll>>; 
  13.  
  14. template <class T>
  15. using v = vector<T>;
  16.  
  17. const int INF_INT = 1e9;
  18. const ll INF_LL = (1LL << 60);
  19. const int MOD = 1000000007;
  20.  
  21.  
  22. int main(){
  23.  
  24.     ll n , v ; 
  25.  
  26.     cin>>n>>v; 
  27.  
  28.  
  29.     vector<ll> val(n+5);
  30.     for (ll i = 1; i <= n; i++) {cin >> val[i];}
  31.  
  32.     vector<vector<ll>>gp(n+5); 
  33.     for(ll i = 0 ;i<v;i++){
  34.         ll x ,y  ; 
  35.         cin>>x>>y; 
  36.         gp[x].push_back(y); 
  37.         gp[y].push_back(x); 
  38.     }
  39.  
  40.  
  41.  
  42.     ll  source = 1 ; 
  43.     vector<ll>vis(n+5 , 0); 
  44.     vector<ll>ways(n+5 , 0); 
  45.     vector<ll>level(n+5 , 0) ; 
  46.     queue<ll>q; 
  47.     q.push(source);
  48.     vis[source] =  1 ; 
  49.     level[source] = 0 ; 
  50.  
  51.  
  52.     vector<ll>fives(n+5, 0 ); 
  53.     vector<ll>fives_second_round(n+5, 0) ; 
  54.       if(val[1]==5)fives[1] = 1 ; 
  55.     while(!q.empty()){
  56.         ll ele = q.front(); 
  57.         q.pop(); 
  58.  
  59.         for(auto x  : gp[ele]){
  60.             if(vis[x]==0){
  61.  
  62.                 vis[x] = 1 ; 
  63.                 level[x] = level[ele] + 1 ; 
  64.                 if(val[x]==5){
  65.                     fives[x] = fives[ele]  + 1 ;
  66.  
  67.                 }
  68.                 else{
  69.                     fives[x] = fives[ele] + 0 ; 
  70.                 }
  71.                  q.push(x); 
  72.             } 
  73.             else{
  74.                 if(level[ele] + 1 == level[x]){
  75.                     ll  temp; 
  76.                     if(val[x]==5){
  77.                        temp =fives[ele] +1  ;  
  78.                     }
  79.                     else{
  80.                         temp = fives[ele]; 
  81.                     }
  82.  
  83.                     if(temp > fives[x]){
  84.                         fives[x] = temp; 
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.     }
  90.  
  91.  
  92.  
  93.     //**Second round required to  get the final  value of 5's for the node x */
  94.  
  95.     cout<<endl ; 
  96.     vis.assign(n+5,0); 
  97.     level.assign(n+5,0); 
  98.  
  99.     q.push(source) ; 
  100.     vis[source] =  1 ; 
  101.     level[source] = 0 ; 
  102.       ways[1] = 1 ; 
  103.       if(val[1]==5){
  104.         fives_second_round[1] = 1 ;
  105.       }
  106.        while(!q.empty()){
  107.         ll ele = q.front(); 
  108.  
  109.         cout<<ele<<" "<<ways[ele]<<endl;//printing that node with its number of ways to visit 
  110.         q.pop(); 
  111.  
  112.         for(auto x  : gp[ele]){
  113.             if(vis[x]==0){
  114.                 vis[x] = 1 ; 
  115.                 level[x] = level[ele] + 1 ; 
  116.                 if(val[x]==5){
  117.                     fives_second_round[x] = fives_second_round[ele]  + 1 ;  
  118.                 }
  119.                 else{
  120.                     fives_second_round[x] = fives_second_round[ele] + 0 ;
  121.                 }
  122.                 if(fives_second_round[x] == fives[x])ways[x] = ways[ele] + ways[x]; 
  123.                  q.push(x); 
  124.             } 
  125.             else{
  126.                 if(level[ele] + 1 == level[x]){
  127.                     ll  temp; 
  128.                     if(val[x]==5){
  129.                        temp =fives_second_round[ele] +1  ;  
  130.                     }
  131.                     else{
  132.                         temp = fives_second_round[ele]; 
  133.                     }
  134.  
  135.                     if(temp > fives_second_round[x]){
  136.                         fives_second_round[x] = temp; 
  137.  
  138.                     }
  139.                     if(temp == fives[x]){
  140.                         ways[x] = ways[ele] + ways[x] ; 
  141.                     }
  142.                 }
  143.             }
  144.         }
  145.     }
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.     return 0 ;
  155. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
8 8 
0 5 5 5 0 5 5 5 
1 2
2 3 
3 4 
4 5 
1 6
6 7
7 8 
8 5
stdout 
1 1
2 1
6 1
3 1
7 1
4 1
8 1
5 2
https://ideone.com/SFHG57
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!