fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define forI(i,a,b) for(int i=(a);i<(b);i++)
  3. #define forD(i,a,b) for(int i=(a);i>(b);--i)
  4. #define ll long long
  5. #define FOUND 1
  6. #define NOTFOUND 0
  7. #define MAXSIZE 10000
  8. #define pb push_back
  9. using namespace::std;
  10.  
  11. typedef vector <int> vi;
  12. typedef vector<vi> vvi;
  13. typedef pair < int, int > ii;
  14. typedef vector < ii > vii;
  15. typedef vector <vii> vvii;
  16. void dfs(vvi &g, int v, vector <bool> &vs)
  17. {
  18.     vs[v] = true;
  19.     for(auto it = g[v].begin() ; it != g[v].end() ; ++it)
  20.         if(!vs[*it])
  21.         dfs(g, *it, vs);
  22. }
  23. ll unsigned Kingcon(vvi &g, int V)
  24. {
  25.     vector <bool> vs(V, false);
  26.     int count = 0;
  27.     /*approch is to identify the elements which will affect the unity of the kingdom if attacked
  28.     by setting a particular node visited and then call dfs on any of the rest of the nodes
  29.     if any node remains unvisited, the node which was set visited requires shield*/
  30.     forI(i,0,V)
  31.     {
  32.         vs[i] = true;
  33.         if(i == V-1)    dfs(g, i-1, vs);
  34.         else dfs(g, i+1, vs);
  35.         for(auto it : vs)
  36.             if(it == false)             //if any node remains unvisited ...
  37.         {
  38.             count++;                    //increment the shield by 1
  39.             break;
  40.         }
  41.         //else do nothing, as taking this node away 4m d graph could not affect unity of the kingdom,
  42.         // dfs on any node still manages to visit the rest of the nodes
  43.  
  44.         for(int i = 0 ; i < V ; ++i)    //reset visited status of all the nodes to check the shield requirement of next node
  45.             vs[i] = false;
  46.     }
  47.     return count;
  48. }
  49. int main()
  50. {
  51.     ll unsigned T, N, M, K,s, d;
  52.     //cout<<"\nenter the test cases :\t";
  53.     cin>>T;
  54.     //cout<<"\nenter no. of cities, roads, and cost of shield :\n";
  55.     cin>>N>>M>>K;
  56.  
  57.     vvi g(N);
  58.  
  59.     //cout<<"\nenter connected roads :\t";
  60.     for(int i = 0 ; i < M ; ++i)
  61.     {
  62.         cin>>s>>d;
  63.         g[s].pb(d);
  64.         g[d].pb(s);
  65.     }
  66.     //cout<<"\nthe amount required for minimum no of shields is :\t"<<endl;
  67.     cout<<Kingcon(g, N)*K;
  68.     return 0;
  69. }
  70.  
Runtime error #stdin #stdout #stderr 0s 4324KB
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/6b5590
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!