fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<time.h>
  3. #define llu long long unsigned
  4. #define MAXSIZE 10000
  5. #define pb push_back
  6.  
  7. using namespace::std;
  8.  
  9. typedef vector <int> vi;
  10. typedef pair < int, int > ii;
  11. typedef vector < ii > vii;
  12. typedef vector <vii> vvii;
  13. typedef vector < vi > vvi;
  14.  
  15. //r2 keeps track of the no. of open window children of root of /**each**/ tree in the forest
  16. map <int, llu> r2;
  17. map <int, llu> aux_map;
  18. vi tree;
  19. vector <int> track;
  20. vector <bool> vs;
  21. //class disjoint_sets
  22. //{
  23. //    public :
  24. //
  25. //    unordered_map <int, int > parent;
  26. //    unordered_map <int, int > rank;
  27. //
  28. //    //constructor
  29. //    disjoint_sets(deque <int> &universe)
  30. //    {
  31. //        for(int x : universe)//for(auto it = universe.begin() ; it != universe.end() ; ++it)     //: line no nodes req
  32. //        {
  33. //            parent[x] = x;
  34. //            rank[x] = 0;
  35. //        }
  36. //    }
  37. //    int find(int item)
  38. //    {
  39. //        if(parent[item] == item)
  40. //            return item;
  41. //        else return find(parent[item]);
  42. //    }
  43. //    void unite(int a, int b)
  44. //    {
  45. //        int a_parent  = find(a);
  46. //        int b_parent  = find(b);
  47. //        if(rank[a_parent] > rank[b_parent])
  48. //        {
  49. //            parent[b_parent] = a_parent;
  50. //            rank[a_parent] += rank[b_parent];
  51. //        }
  52. //        else if(rank[a_parent] < rank[b_parent])
  53. //        {
  54. //            parent[a_parent] = b_parent;
  55. //            rank[b_parent] += rank[a_parent];
  56. //        }
  57. //        else
  58. //        {
  59. //            parent[a_parent] = b_parent;
  60. //            rank[b_parent] ++;
  61. //        }
  62. //    }
  63. //    void disp()
  64. //    {
  65. //        for(pair < int, int >  p : parent)    //for(auto it = parent.begin() ; it != parent.end() ; ++it)
  66. //            cout<<p.second<<" ";
  67. //    }
  68. //};
  69.  
  70. int dfs_fun(vvi &g, int x, vector <int> &key, vector <bool> &vs)   //function for second query
  71. {
  72.     vs[x] = true;
  73.     int res = (key[x] == 1) ? 1 :0;
  74.  
  75.     for(auto it : g[x])
  76.         if(!vs[it])
  77.     {
  78.         if(key[it] == 1)
  79.                 {
  80.                     vs[it] = true;
  81.                     return 1;
  82.                 }
  83.  
  84.         res = dfs_fun(g, it, key, vs);
  85.         if(res) return res;
  86.     }
  87.         return res;
  88. }
  89.  
  90. llu dfs(vvi &g, vector <bool> &vs, int v, vi &key)
  91. {
  92.     vs[v] = true;
  93.     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
  94.     for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
  95.  
  96.             if(!vs[*it])
  97.         c += dfs(g, vs, *it, key);                          //increment c by the no of open window nodes rooted at c
  98.  
  99.  
  100.     if(key[v])      {
  101.                     r2[v] = c ;                                 //map r2 keeps track of no. of open window nodes rooted at each node of the graph
  102.                     return c ;
  103.                     }
  104.     {
  105.         r2[v] = c-1 ;                                          //if the node has its window closed,adjust its contribution which was initiated as 1
  106.         return c-1;
  107.     }
  108. }
  109.  
  110. void drought(vvi &g, vi &key, int V, vi &r1)
  111. {
  112.     vs = vector<bool> (V+1, false);
  113.     vs[0] = true;
  114.     for(int i = 1 ; i <= V ; ++i)
  115.         if(!vs[i])
  116.     {
  117.         tree.pb(i);                         // the vector tree keeps track of root of each tree in the forest
  118.         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
  119.     }
  120. }
  121.  
  122. long long unsigned calculate(vi tree, map<int, llu> &r2)
  123. {
  124.     long long unsigned count = 0;
  125.     for(auto it : tree)
  126.         count += (r2[it]*(r2[it]-1))/2;
  127.     return count;
  128. }
  129.  
  130. int main()
  131. {
  132. //    ios_base::sync_with_stdio(0);
  133. //    cin.tie(0);
  134.     srand(time(0));
  135.     track.reserve(50050);
  136.     tree.reserve(50050);
  137.     int V, E, s, d, w, st, auxi = 0;
  138.  
  139.     //cout<<"\nenter the no of nodes and edges :\t ";
  140.     cin>>V>>E;
  141.  
  142.     //deque <int> aux;
  143. //    for(int i = 0; i < V ; ++i)   aux.pb(i+1);
  144. //    disjoint_sets dso(aux);
  145.  
  146.     for(int i = 0 ; i <= V ; ++i)   r2[i] = 0;
  147.  
  148.     tree.pb(0);
  149.     vi r1;
  150.     vi key(V+1);
  151.     vvi g(V+1);
  152.  
  153.      //cout<<"\nenter the window status \n";
  154.     key[0] = 0;
  155.  
  156.     for(int i = 1 ;  i <= V ; ++i)
  157.         {
  158.             //st = rand()%2;
  159.             cin>>st;
  160.             key[i] = st;
  161.         }
  162.  
  163.     /**cout<<"\nutilising rand(), the window status and links bw friends that have been formed are :\n";**/
  164.  
  165.  
  166. //    for(int i = 1 ;  i <= V ; ++i)
  167. //        cout<<key[i]<<' ';
  168.     //cout<<"\nenter each edge\n";
  169.         for(int i = 0 ; i < E ;++i)
  170.     {
  171.             cin>>s;
  172.             cin>>d;
  173.             g[s].pb(d);
  174.             g[d].pb(s);
  175.     }
  176.  
  177.  
  178.     drought(g, key, V, r1);
  179.  
  180. //     cout<<"\nno of open window children rooted @ a prticular node(including its own status) : node -> open window children "<<endl;
  181. //     cout<<"\nigonre the case for 0"<<endl;
  182. //     for(auto it : r2)
  183. //        cout<<it.first<<" -> "<<it.second<<endl;
  184. ///****************************************************************************************************************************/
  185.     //cout<<"\nanswer to query 1 is : \t";
  186.        cout<<calculate(tree, r2)<<' ';
  187.  
  188.         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
  189.         auto it1 = tree.begin()+1;         //root of the very first tree
  190.         auto it2 = it1+1;                  //root of the next tree
  191.         llu rubik = 0;
  192.         vector <int> remaining;
  193.  
  194. //        cout<<"\n3 cases for second answer :";
  195. //        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";
  196. //        cout<<"\n2.element has its window open and has at least one open window child, hence the path bw them connects 'em";
  197. //        cout<<"\n3.else the node must have at least two open window nodes rooted @ itself";
  198.         while(*it1 != V+1)                                  //for root of each tree in the forest do the following
  199.         {
  200.             llu x = *it1 ;                  //first element of the present tree
  201.             llu root_id = r2[x];            //no. of open window nodes rooted @ node x
  202.             while( x < *it2 )               //for each element of the tree rooted at it1 do the following
  203.             {
  204.                 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
  205.                             {rubik++;} //cout<<"\t 1. "<<x<<endl;}
  206.  
  207.                     else {
  208.                             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
  209.                             {rubik++;} //cout<<"\t 2. "<<x<<endl;}
  210.  
  211.                                 else                                  //else for the element must have at least two open window nodes rooted @ itself
  212.                                 remaining.pb(x);
  213.                          }                   //store these elements in a vector, w'll deal with those later, this requires another loop
  214.             x++;
  215.             }
  216.             it1++;                  /*increment the tree*/
  217.             it2++;
  218.  
  219.         }
  220. //        for(auto it : remaining)
  221. //            cout<<"\n"<<"3. "<<it<<endl;
  222.             for(auto it : remaining)
  223.         {
  224.             vs = vector<bool> (V+1, false);
  225.             track = vector<int> (V+1, 0);
  226.             int i = 0;
  227.  
  228.             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
  229.                 {
  230.                     track.pb(dfs_fun(g, it, key, vs));
  231.                     i++;
  232.                 }
  233.                 if(count(begin(track), end(track), 1)>=2) {rubik++;} //cout<<"\n"<<it<<" contributes towards the second answer";}
  234.         }
  235.         //cout<<"the result of query 2 is :\t";
  236.         cout<<rubik<<endl;
  237.  
  238.         return 0;
  239. }
  240.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
100 99
0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 
15 80
88 100
52 15
96 43
22 99
76 92
86 15
72 6
49 95
38 11
61 56
70 48
66 8
73 43
82 50
55 96
29 42
47 32
8 42
26 29
92 1
21 77
16 44
83 16
38 20
26 99
27 95
46 92
55 18
87 88
19 41
83 48
34 81
31 41
23 9
69 14
61 41
43 28
85 25
44 22
96 21
20 74
68 18
66 74
87 52
61 6
44 43
5 77
23 87
17 97
95 85
63 56
78 5
83 62
81 78
83 76
72 66
39 10
69 51
67 12
45 71
40 67
10 56
16 4
93 78
82 46
31 14
75 65
90 42
7 80
4 27
30 70
91 74
86 60
37 68
65 81
97 75
64 16
15 53
9 21
85 12
71 36
3 98
22 36
39 13
48 35
17 94
40 79
80 58
16 84
15 47
33 14
67 57
3 73
59 65
43 54
64 24
2 73
89 8
stdout
copy 
1485 77
https://ideone.com/IYPIzo
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!