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 open window children of root of /**each**/ tree in the forest
  14. map <int, llu> r2;
  15. map <int, llu> aux_map;
  16. vi tree;
  17. vector <bool> track;
  18. vector <bool> vs;
  19.  
  20. bool dfs_fun(vvi &g, int x, vector <int> &key, vector <bool> &vs)
  21. {
  22.     vs[x] = true;
  23.     bool res = false;
  24.     for(auto it : g[x])
  25.         if(!vs[it])
  26.     {
  27.         vs[it] = true;
  28.         if(key[it] == 1)
  29.         {
  30.             res = true;
  31.             break;
  32.         }
  33.         else res = dfs_fun(g, it, key, vs);
  34.     }
  35.     return res;
  36. }
  37.  
  38. llu dfs(vvi &g, vector <bool> &vs, int v, map <int, llu> &r2, vi &key)
  39. {
  40.     vs[v] = true;
  41.     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
  42.     for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
  43.  
  44.             if(!vs[*it])
  45.         c += dfs(g, vs, *it, r2, key);                          //increment c by the no of open window nodes rooted at c
  46.  
  47.  
  48.     if(key[v])      {
  49.                     r2[v] = c ;                                 //map r2 keeps track of no. of open window nodes rooted at each node of the graph
  50.                     return c ;
  51.                     }
  52.     {
  53.         r2[v] = c-1 ;                                          //if the node has its window closed,adjust its contribution which was initiated as 1
  54.         return c-1;
  55.     }
  56. }
  57.  
  58. void drought(vvi &g, vi &key, int V, vi &r1)
  59. {
  60.     vs = vector<bool> (V+1, false);
  61.     vs[0] = true;
  62.     for(int i = 1 ; i <= V ; ++i)
  63.         if(!vs[i])
  64.     {
  65.         tree.pb(i);                         // the vector tree keeps track of root of each tree in the forest
  66.         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
  67.     }
  68. }
  69.  
  70. long long unsigned calculate(vi tree, map<int, llu> &r2)
  71. {
  72.     long long unsigned count = 0;
  73.     for(auto it =  tree.begin() ; it != tree.end() ; ++it)
  74.         count += (r2[*it]*(r2[*it]-1))/2;
  75.     return count;
  76. }
  77.  
  78. int main()
  79. {
  80.     /*ios_base::sync_with_stdio(0);
  81.     cin.tie(0);*/
  82.  
  83.     int V, E, s, d, w, st;
  84.  
  85.     //cout<<"\nenter the no of nodes and edges :\t ";
  86.     cin>>V>>E;
  87.  
  88.     for(int i = 0 ; i <= V ; ++i)
  89.         {
  90.             r2[i] = 0;
  91.             aux_map[i] = 0;
  92.         }
  93.  
  94.     tree.pb(0);
  95.     vi r1;
  96.     vi key(V+1);
  97.     vvi g(V+1);
  98.  
  99.      //cout<<"\nenter the window status \n";
  100.     key[0] = 0;
  101.     for(int i = 1 ;  i <= V ; ++i)
  102.         {
  103.             cin>>st;
  104.             key[i] = st;
  105.         }
  106.  
  107.     //cout<<"\nenter each edge\n";
  108.     for(int i = 0 ; i < E ; ++i)
  109.     {
  110.         cin>>s>>d;
  111.         g[s].pb(d);
  112.         g[d].pb(s);
  113.     }
  114.  
  115.     drought(g, key, V, r1);
  116.  
  117.      /*cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "<<endl;
  118.      cout<<"\nigonre the case for 0"<<endl;
  119.      for(auto it : r2)
  120.         cout<<it.first<<" -> "<<it.second<<endl;*/
  121.  
  122. //    cout<<"\nanswer to query 1 is : \t";
  123.        cout<<calculate(tree, r2)<<' ';
  124.  
  125.         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
  126.         auto it1 = tree.begin()+1;            //root of the very first tree
  127.         auto it2 = it1;
  128.         it2++;                              //root of the next tree
  129.         llu rubik = 0;
  130.         vector <tuple<int, int, int> > remaining;
  131.  
  132.         do                                  //for root of each tree in the forest do the following
  133.         {
  134.             llu x = *it1 ;                  //first element of the present tree
  135.             llu root_id = r2[x];            //no. of open window nodes rooted @ node x
  136.             while( x < *it2 )               //for each element of the tree rooted at it1 do the following
  137.             {
  138.                 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
  139.                             rubik++;
  140.  
  141.                     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
  142.                             rubik++;
  143.  
  144.                     else                                  //else for the element must have at least two open window nodes rooted @ itself
  145.                         remaining.pb(make_tuple(x, *it1, *it2));
  146.             x++;
  147.             }
  148.             it1++;                  /*increment the tree*/
  149.             it2++;
  150.  
  151.         }while(*it1 != V+1);
  152.         /*cout<<"\ntuple is :\t";
  153.         for(auto it : remaining)     cout<<get<0>(it)<<' '<<get<1>(it)<<' '<<get<2>(it)<<"\t";*/
  154.         for(auto it : remaining)
  155.         {
  156.             vs = vector<bool> (get<2>(it) - get<1>(it), false);
  157.             track = vector<bool> (get<2>(it) - get<1>(it), false);
  158.             int i = 0;
  159.             while(count(begin(track), end(track), true)<2 && i < g[get<0>(it)].size())
  160.                 {
  161.                     track[i] = dfs_fun(g, get<0>(it) , key, vs);
  162.                     i++;
  163.                 }
  164.                 if(count(begin(track), end(track), true)>=2) rubik++;
  165.         }
  166.         //cout<<"\nthe result of query 2 is :\t";
  167.         cout<<rubik<<endl;
  168.  
  169.         return 0;
  170. }
  171.  
Runtime error #stdin #stdout #stderr 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/awrIaJ
language:
C++14 (gcc 8.3)
created:
9 years 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!