fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define llu long long unsigned
  3. #define MAXSIZE 10000
  4. #define pb push_back
  5. using namespace::std;
  6.  
  7. typedef vector <int> vi;
  8. typedef pair < int, int > ii;
  9. typedef vector < ii > vii;
  10. typedef vector <vii> vvii;
  11. typedef vector < vi > vvi;
  12.  
  13. //r2 keeps track of the no. of children of root of /**each**/ tree in the forest which are labeled 1
  14. map <int, llu> r2;
  15. map <int, llu> aux_map;
  16. vi tree;
  17.  
  18. llu dfs(vvi &g, vector <bool> &vs, int v, map <int, llu> &r2, vi &key)
  19. {
  20.     vs[v] = true;
  21.     llu  c = 1;                                                  //contribution of the node on which dfs has been called, ...we'll return c-1 later if this nodes window is closed
  22.     for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
  23.  
  24.             if(!vs[*it])
  25.         c += dfs(g, vs, *it, r2, key);                          //increment c by the no of open window nodes rooted at c
  26.  
  27.  
  28.     if(key[v])      {
  29.                     r2[v] = c ;                                 //map r2 keeps track of no. of open window nodes rooted at each node of the graph
  30.                     return c ;
  31.                     }
  32.     {
  33.         r2[v] = c-1 ;                                          //if the node has its window closed,adjust its contribution which was initiated as 1
  34.         return c-1;
  35.     }
  36. }
  37.  
  38. void drought(vvi &g, vi &key, int V, vi &r1)
  39. {
  40.     vector <bool> vs(V+1, false);
  41.     vs[0] = true;
  42.  
  43.     for(int i = 1 ; i <= V ; ++i)
  44.         if(!vs[i])
  45.     {
  46.         tree.pb(i);                         // the vector tree keeps track of root of each tree in the forest
  47.         r1.pb(dfs(g, vs, i, r2, key));      //the vector r1 stores the no of 'open window' nodes rooted at each root of the forest including the status of root
  48.     }
  49. }
  50.  
  51. long long unsigned calculate(vi tree, map<int, llu> &r2)
  52. {
  53.     long long unsigned count = 0;
  54.     for(auto it =  tree.begin() ; it != tree.end() ; ++it)
  55.         count += (r2[*it]*(r2[*it]-1))/2;
  56.     return count;
  57. }
  58. int main()
  59. {
  60.     int V, E, s, d, w, st;
  61.  
  62.     //cout<<"\nenter the no of nodes and edges :\t ";
  63.     cin>>V>>E;
  64.  
  65.     for(int i = 0 ; i <= V ; ++i)
  66.         {
  67.             r2[i] = 0;
  68.             aux_map[i] = 0;
  69.         }
  70.  
  71.     vi r1;
  72.     vi key(V+1);
  73.     vvi g(V+1);
  74.  
  75.      //cout<<"\nenter the window status \n";
  76.     key[0] = 0;
  77.     for(int i = 1 ;  i <= V ; ++i)
  78.         {
  79.             cin>>st;
  80.             key[i] = st;
  81.         }
  82.  
  83.     //cout<<"\nenter each edge\n";
  84.     for(int i = 0 ; i < E ; ++i)
  85.     {
  86.         cin>>s>>d;
  87.         g[s].pb(d);
  88.         g[d].pb(s);
  89.     }
  90.  
  91.     drought(g, key, V, r1);
  92.  
  93.      /*cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "<<endl;
  94.      cout<<"\nigonre the case for 0"<<endl;
  95.      for(auto it : r2)
  96.         cout<<it.first<<" -> "<<it.second<<endl;*/
  97.  
  98.        // cout<<"\nanswer to query 1 is : \t";
  99.        cout<<calculate(tree, r2)<<' ';
  100.  
  101.         tree.pb(V+1);                      // last element of the vector tree contains V+1 to make the do while loop (to find answer to query 2)ahead functional
  102.         auto it1 = tree.begin();            //root of the very first tree
  103.         auto it2 = it1;
  104.         it2++;                              //root of the next tree
  105.         llu count = 0;
  106.  
  107.         do                                  //for root of each tree in the forest do the following
  108.         {
  109.             llu x = *it1 ;                  //first element of the present tree
  110.             llu root_id = r2[x];            //no. of open window nodes rooted @ node x
  111.             while( x < *it2 )               //for each element of the tree rooted at it1 do the following
  112.             {
  113.                 if(r2[x] > 0 && r2[x] < root_id)            //element has at least 1 open window child also there is some open window node rooted at the same root at which the element is hence at least the way between these 2 nodes connects 'em
  114.                             count++;
  115.  
  116.                     else if(key[x] == 1 && r2[x] > 1)       //element has its window open and has at least one open window child, hence the path bw them connects 'em
  117.                             count++;
  118.  
  119.                     else                                  //else for the element must have at least two open window nodes rooted @ itself
  120.                     {
  121.                         vector <bool> vsz(x - *it1, true);      //mark all the nodes b4 x visited as we are interested to find the no. of open window nodes of subtree rooted @ x
  122.                         for(llu i = x ; i < *it2 ; ++i)         //mark all the remaining nodes(including itself) in the tree unvisited
  123.                             vsz[i] = false;
  124.                         if(key[x])                              //if the node has its window open calling dfs on it returns 1+no. of open window nodes rooted @ it
  125.                         {
  126.                             if(dfs(g, vsz, x, aux_map, key) >= 3)
  127.                             count++;
  128.                         }
  129.                         else if(dfs(g, vsz, x, aux_map, key) >= 2)          //else if the node has its window closed calling dfs on it returns no. of open window nodes rooted @ it
  130.                             count++;
  131.                     }
  132.             x++;
  133.                 }
  134.             it1++;                  /*increment the tree*/
  135.             it2++;
  136.  
  137.         }while(*it1 != V+1);
  138.         //cout<<"\nthe result of query 2 is :\t";
  139.         cout<<count<<endl;
  140.  
  141.         return 0;
  142. }
  143.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
5 4
1 0 0 1 1
1 2
2 4
4 5
5 3
stdout
copy 
3 5
https://ideone.com/OKo0Ni
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!