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 <int> track;
  18. vector <bool> vs;
  19.  
  20. int dfs_fun(vvi &g, int x, vector <int> &key, vector <bool> &vs)   //function for second query
  21. {
  22.     vs[x] = true;
  23.     int res = (key[x] == 1) ? 1 :0;
  24.  
  25.     for(auto it : g[x])
  26.         if(!vs[it])
  27.     {
  28.         if(key[it] == 1)
  29.                 {
  30.                     vs[it] = true;
  31.                     return 1;
  32.                 }
  33.  
  34.         res = dfs_fun(g, it, key, vs);
  35.         if(res) return res;
  36.     }
  37.         return res;
  38. }
  39.  
  40. llu dfs(vvi &g, vector <bool> &vs, int v, vi &key)
  41. {
  42.     vs[v] = true;
  43.     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
  44.     for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
  45.  
  46.             if(!vs[*it])
  47.         c += dfs(g, vs, *it, key);                          //increment c by the no of open window nodes rooted at c
  48.  
  49.  
  50.     if(key[v])      {
  51.                     r2[v] = c ;                                 //map r2 keeps track of no. of open window nodes rooted at each node of the graph
  52.                     return c ;
  53.                     }
  54.     {
  55.         r2[v] = c-1 ;                                          //if the node has its window closed,adjust its contribution which was initiated as 1
  56.         return c-1;
  57.     }
  58. }
  59.  
  60. void drought(vvi &g, vi &key, int V, vi &r1)
  61. {
  62.     vs = vector<bool> (V+1, false);
  63.     vs[0] = true;
  64.     for(int i = 1 ; i <= V ; ++i)
  65.         if(!vs[i])
  66.     {
  67.         tree.pb(i);                         // the vector tree keeps track of root of each tree in the forest
  68.         r1.pb(dfs(g, vs, i, key));      //the vector r1 stores the no of 'open window' nodes rooted at each root of the forest including the status of root
  69.     }
  70. }
  71.  
  72. long long unsigned calculate(vi tree, map<int, llu> &r2)
  73. {
  74.     long long unsigned count = 0;
  75.     for(auto it : tree)
  76.         count += (r2[it]*(r2[it]-1))/2;
  77.     return count;
  78. }
  79.  
  80. int main()
  81. {
  82. //    ios_base::sync_with_stdio(0);
  83. //    cin.tie(0);
  84.     track.reserve(50050);
  85.     tree.reserve(50050);
  86.     int V, E, s, d, w, st;
  87.  
  88.     //cout<<"\nenter the no of nodes and edges :\t ";
  89.     cin>>V>>E;
  90.  
  91.     for(int i = 0 ; i <= V ; ++i)
  92.  
  93.             r2[i] = 0;
  94.  
  95.     tree.pb(0);
  96.     vi r1;
  97.     vi key(V+1);
  98.     vvi g(V+1);
  99.  
  100.      //cout<<"\nenter the window status \n";
  101.     key[0] = 0;
  102.     for(int i = 1 ;  i <= V ; ++i)
  103.         {
  104.             cin>>st;
  105.             key[i] = st;
  106.         }
  107.  
  108.     //cout<<"\nenter each edge\n";
  109.     for(int i = 0 ; i < E ; ++i)
  110.     {
  111.         cin>>s>>d;
  112.         g[s].pb(d);
  113.         g[d].pb(s);
  114.     }
  115.  
  116.     drought(g, key, V, r1);
  117.  
  118.      cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "<<endl;
  119.      cout<<"\nigonre the case for 0"<<endl;
  120.      for(auto it : r2)
  121.         cout<<it.first<<" -> "<<it.second<<endl;
  122. /****************************************************************************************************************************/
  123.     cout<<"\nanswer to query 1 is : \t";
  124.        cout<<calculate(tree, r2)<<endl;
  125.  
  126.         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
  127.         auto it1 = tree.begin()+1;         //root of the very first tree
  128.         auto it2 = it1+1;                  //root of the next tree
  129.         llu rubik = 0;
  130.         vector <int> remaining;
  131.  
  132.         cout<<"\n3 cases for second answer :";
  133.         cout<<"\n1.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";
  134.         cout<<"\n2.element has its window open and has at least one open window child, hence the path bw them connects 'em";
  135.         cout<<"\n3.else the node must have at least two open window nodes rooted @ itself";
  136.         while(*it1 != V+1)                                  //for root of each tree in the forest do the following
  137.         {
  138.             llu x = *it1 ;                  //first element of the present tree
  139.             llu root_id = r2[x];            //no. of open window nodes rooted @ node x
  140.             while( x < *it2 )               //for each element of the tree rooted at it1 do the following
  141.             {
  142.                 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
  143.                             {rubik++; cout<<"\t 1. "<<x<<endl;}
  144.  
  145.                     else {
  146.                             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
  147.                             {rubik++;cout<<"\t 2. "<<x<<endl;}
  148.  
  149.                                 else                                  //else for the element must have at least two open window nodes rooted @ itself
  150.                                 remaining.pb(x);
  151.                          }                   //store these elements in a vector, w'll deal with those later, this requires another loop
  152.             x++;
  153.             }
  154.             it1++;                  /*increment the tree*/
  155.             it2++;
  156.  
  157.         }
  158.         for(auto it : remaining)
  159.             cout<<"\n"<<"3. "<<it<<endl;
  160.             for(auto it : remaining)
  161.         {
  162.             vs = vector<bool> (V+1, false);
  163.             track = vector<int> (V+1, 0);
  164.             int i = 0;
  165.  
  166.             while(count(begin(track), end(track), 1)<2 && i < g[it].size())          //loop till either we find at least 2 open window children rooted at concerned node 'x' (lying in remaining) or we visit all adj nodes of x
  167.                 {
  168.                     track.pb(dfs_fun(g, it, key, vs));
  169.                     i++;
  170.                 }
  171.                 if(count(begin(track), end(track), 1)>=2) { rubik++; cout<<"\n"<<it<<" contributes towards the second answer";}
  172.         }
  173.         cout<<"\nthe result of query 2 is :\t";
  174.         cout<<rubik<<endl;
  175.  
  176.         return 0;
  177. }
  178.  
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
15 13
1 0 0 1 1 0 0 0 0 0 0 1 0 0 1
1 2
2 4
4 5
3 5
3 6
7 8
8 10
8 11
11 15
7 9
9 12
9 13
13 14
stdout
copy 
no of open window children rooted @ a prticular node(including its own status) : node -> open window children 

igonre the case for 0
0 -> 0
1 -> 3
2 -> 2
3 -> 0
4 -> 2
5 -> 1
6 -> 0
7 -> 2
8 -> 1
9 -> 1
10 -> 0
11 -> 1
12 -> 1
13 -> 0
14 -> 0
15 -> 1

answer to query 1 is : 	4

3 cases for second answer :
1.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
2.element has its window open and has at least one open window child, hence the path bw them connects 'em
3.else the node must have at least two open window nodes rooted @ itself	 2. 1
	 1. 2
	 1. 4
	 1. 5
	 1. 8
	 1. 9
	 1. 11
	 1. 12
	 1. 15

3. 3

3. 6

3. 7

3. 10

3. 13

3. 14

7 contributes towards the second answer
the result of query 2 is :	10
https://ideone.com/72P7ol
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!