fork(2) download
copy 
  1. # include <iostream>
  2. # include <stdio.h>
  3. # include <algorithm>
  4. # include <queue>
  5. # include <set>
  6. # include <string.h>
  7. # include <vector>
  8. # include <fstream>
  9. # include <math.h>
  10. # include <sstream>
  11. # include <stack>
  12.  
  13. # define for1(i,k,n)              for(long long i=k;i<n;i++)
  14. # define for2(i,k,n)              for(long long i=k;i<=n;i++)
  15. # define Min(x,y)                   ((x)<(y)?(x):(y))
  16. # define Max(x,y)                   ((x)>(y)?(x):(y))
  17. # define INF (long long int ) 1e15
  18. # define ALL(x)                  (begin(x),end(x))
  19. # define Abs(x)                 (x>=0?x:-x)
  20.  
  21. using namespace std;
  22. typedef long long int ll;
  23.  
  24. ll time1,sum1;
  25. vector< vector<int> > g;
  26. vector <int> status;
  27. vector <int> parent;
  28. vector <int> low;
  29. vector <int> in;
  30. vector <int> fin;
  31. vector <int> child;
  32. vector <bool> check;
  33. void dfs (int x)
  34. {
  35. 	++time1; 
  36. 	low[x]=time1;// min dfs in the subtree rooted at x,initialised to be dfs no of x
  37. 	in[x]=time1; //dfs number for x stored in in x
  38. 		if (status[x]!=0)
  39. 			return;
  40. 		status[x]=1;
  41. 		for1(i,0,g[x].size())
  42. 		{   //normal dfs going on
  43. 			if (status[g[x][i]]==0)
  44. 			{
  45. 				parent[g[x][i]]=x;
  46. 				++child[x];
  47. 				dfs(g[x][i]);
  48. 			}
  49. 		}
  50. 		status[x]=2;
  51. for1(i,0,g[x].size())
  52. {
  53. 	if (g[x][i]!=parent[x])
  54. 	{
  55. 		low[x]=Min(low[x],low[g[x][i]]);  // now the minimum vertex acessed by x except that of its parent
  56. 	}
  57. }
  58. 	}
  59.  
  60.  
  61.  
  62.  
  63.  
  64.   int main()
  65. {
  66.  #ifndef ONLINE_JUDGE
  67.     freopen("in.txt", "r", stdin);
  68. #endif
  69.     std::ios_base::sync_with_stdio (false);
  70.  
  71.     ll i,j,k,x,y,l,n,m,t,sum1;
  72.  
  73. cin>>t;
  74. while(t--)
  75. {sum1=0; time1=0;
  76. 	cin>>n>>m>>k;
  77. 	g.clear();
  78. 	child.clear();
  79. 	in.clear();
  80. 	fin.clear();
  81. 	status.clear();
  82. 	check.clear();
  83. 	low.clear();
  84. 	parent.clear();
  85. 	g.resize(n);
  86. 	in.resize(n);
  87. 	fin.resize(n);
  88. 	status.resize(n);
  89. 	low.resize(n);
  90. 	child.resize(n);
  91. 	parent.resize(n);
  92. 	check.resize(n);
  93. 	fill(check.begin(),check.end(),false);
  94. 	fill(parent.begin(),parent.end(),-1);
  95. 	fill(status.begin(),status.end(),0);
  96. 	fill(child.begin(),child.end(),0);
  97. 	for1(i,0,m)
  98. 	{
  99. 		cin>>x>>y;
  100. 		g[x].push_back(y);
  101. 		g[y].push_back(x);
  102. 	}
  103. 	for1(i,0,n)
  104. 	{
  105. 		if (status[i]==0)  // normal dfs
  106. 			dfs(i);
  107. 	}
  108. 	for1(i,0,n)
  109. 	{
  110. 		if ((parent[i]==-1)&&(child[i]>1))
  111. 			++sum1;  // for root
  112. 		if ((parent[i]!=-1)&&(child[i]>0))
  113. 		{// for non root and non leaf
  114. 			for1(j,0,g[i].size())
  115. 			{
  116. 				if (low[g[i][j]]>=in[i])
  117. 				{  //  checking its children and the increasing sum1 where the count is kept
  118. 					++sum1;
  119. 					break;
  120. 				}
  121. 			}
  122. 		}
  123. 	}
  124. cout<<sum1*k<<endl;
  125. }
  126. return 0;
  127. }
Runtime error #stdin #stdout #stderr 0s 2832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_fill_insert
https://ideone.com/1G9qVs
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!