fork(1) download
copy 
  1. //Tanuj Khattar
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef pair<int,int>   II;
  7. typedef vector< II >      VII;
  8. typedef vector<int>     VI;
  9. typedef vector< VI > 	VVI;
  10. typedef long long int 	LL;
  11.  
  12. #define PB push_back
  13. #define MP make_pair
  14. #define F first
  15. #define S second
  16. #define SZ(a) (int)(a.size())
  17. #define ALL(a) a.begin(),a.end()
  18. #define SET(a,b) memset(a,b,sizeof(a))
  19.  
  20. #define si(n) scanf("%d",&n)
  21. #define dout(n) printf("%d\n",n)
  22. #define sll(n) scanf("%lld",&n)
  23. #define lldout(n) printf("%lld\n",n)
  24. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  25.  
  26. //#define TRACE
  27.  
  28. #ifdef TRACE
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32. 	cerr << name << " : " << arg1 << std::endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. #else
  39. #define trace(...)
  40. #endif
  41.  
  42. //FILE *fin = freopen("in","r",stdin);
  43. //FILE *fout = freopen("out","w",stdout);
  44. const int N = int(1e5)+10;
  45. const int M = int(2e5)+10;
  46. int U[M],V[M],isBridge[M],arr[N],T,cmpno;
  47. int far[N],vis[N],level[N],par[N],root;
  48. VI g[N],tree[N],ans;
  49. queue<int> Q[N];
  50. int adj(int u,int e)
  51. {
  52. 	return U[e]==u?V[e]:U[e];
  53. }
  54. int dfs0(int u,int ee)
  55. {
  56. 	vis[u]=1;int dbe=arr[u]=T++;
  57. 	for(auto e:g[u])
  58. 	{
  59. 		int w = adj(u,e); 
  60. 		if(!vis[w])dbe=min(dbe,dfs0(w,e));
  61. 		else if(e!=ee)dbe=min(dbe,arr[w]);
  62. 	}
  63. 	if(dbe==arr[u] && ee!=-1)isBridge[ee]=1;
  64. 	return dbe;
  65. }
  66. void dfs1(int v)
  67. {
  68. 	vis[v]=1;
  69. 	int currcmp = cmpno;
  70. 	Q[currcmp].push(v);
  71. 	while(!Q[currcmp].empty())
  72. 	{
  73. 		int u = Q[currcmp].front();
  74. 		Q[currcmp].pop();
  75. 		for(auto e:g[u])
  76. 		{
  77. 			int w = adj(u,e);
  78. 			if(vis[w])continue;
  79. 			if(isBridge[e])
  80. 			{
  81. 				cmpno++;
  82. 				tree[cmpno].PB(currcmp);
  83. 				tree[currcmp].PB(cmpno);
  84. 				dfs1(w);
  85. 			}
  86. 			else 
  87. 			{
  88. 				Q[currcmp].push(w);
  89. 				vis[w]=1;
  90. 			}
  91. 		}
  92. 	}
  93. }
  94. void buildBridgeTree()
  95. {
  96. 	SET(vis,0);
  97. 	dfs0(1,-1);
  98. 	SET(vis,0);
  99. 	dfs1(1);
  100. }
  101. void dfs2(int u,int p)
  102. {
  103. 	far[u]=u;par[u]=p;
  104. 	level[u]=level[p]+1;
  105. 	for(auto w :tree[u])
  106. 		if(w!=p)
  107. 		{
  108. 			dfs2(w,u);
  109. 			if(level[far[w]]>level[far[u]])
  110. 				far[u]=far[w];
  111. 		}
  112. }
  113. int getCenter()
  114. {
  115. 	level[0]=-1;
  116. 	dfs2(0,0);
  117. 	int x = far[0];
  118. 	level[x]=-1;
  119. 	dfs2(x,x);
  120. 	int y = far[x];
  121. 	while(level[y]>level[far[x]]/2)y=par[y];
  122. 	level[y]=-1;
  123. 	dfs2(y,y);
  124. 	return y;
  125. }
  126. void dfs(int u,int p,int len)
  127. {
  128. 	bool isLeaf=true;
  129. 	for(auto w:tree[u])
  130. 	{
  131. 		if(w==p)continue;
  132. 		isLeaf=false;
  133. 		if(far[u]==far[w])dfs(w,u,len+1);
  134. 		else dfs(w,u,1);
  135. 	}
  136. 	if(isLeaf)ans.PB(len);
  137. }
  138. int main()
  139. {
  140. 	int n,m,q;
  141. 	si(n);si(m);si(q);
  142. 	for(int i=0;i<m;i++)
  143. 	{
  144. 		scanf("%d %d",U+i,V+i);
  145. 		g[U[i]].PB(i);
  146. 		g[V[i]].PB(i);
  147. 	}
  148. 	buildBridgeTree();
  149. 	root = getCenter();
  150. 	dfs(root,root,0);
  151. 	sort(ALL(ans));reverse(ALL(ans));
  152. 	for(int i=1;i<SZ(ans);i++)ans[i]+=ans[i-1];
  153. 	while(q--)
  154. 	{
  155. 		int k;si(k);k = 2*k;
  156. 		k = min(k,SZ(ans));
  157. 		dout(ans[k-1]);
  158. 	}
  159. 	return 0;
  160. }
Success #stdin #stdout 0.1s 68672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pLCPcP
language:
C++14 (gcc 8.3)
created:
8 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!