fork download
copy 
  1. // Mera solution mat hi dekh yaar!
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long LL;
  7.  
  8. #define inp_s     ios_base::sync_with_stdio(false)
  9. #define DRT()     int test_case;cin>>test_case;while(test_case--)
  10.  
  11. #define VI        vector<int>
  12. #define VS        vector<string>
  13. #define VLL       vector<LL>
  14. #define PII       pair<int,LL>
  15. #define all(c)    c.begin(),c.end()
  16. #define sz(c)     (int)c.size()
  17. #define clr(c)    c.clear()
  18. #define pb        push_back
  19. #define mp        make_pair
  20.  
  21. #define GI(x)     scanf("%d",&x)
  22.  
  23. #define FOR(i,a,b)      for(int i=(int)(a);i<(int)(b);i++)
  24. #define RFOR(i,a,b)     for(int i=(int)(b)-1;i>=(int)(a);i--)
  25.  
  26. #define MOD       1000000007
  27. #define EPS       1E-10
  28.  
  29. #define PI  acos(-1)
  30.  
  31. #define CASE(x)   cout << "Case #" << x << ": ";
  32.  
  33. LL f[1010][1010];
  34. int n,m;
  35. LL mod;
  36.  
  37. LL preprocess(int i , int j)
  38. {
  39. 	if(i == j) return 0;
  40. 	else if(i == 1 || j == 1) return (1%mod);
  41. 	else if(f[i][j] != -1) return f[i][j];
  42. 	LL ret = (preprocess(i-1,j) + preprocess(i,j-1)) % mod;
  43. 	ret = (ret + preprocess(i-1,j-1)) % mod;
  44. 	return (f[i][j] = ret);
  45. }
  46.  
  47. int isBridge[1010][1010];
  48. vector<VI> graph;
  49.  
  50. int dfsTime = 1;
  51. vector<int> low , disc;
  52. int visited[1010];
  53.  
  54. void bridgeDFS(int u , int par)
  55. {
  56. 	if(visited[u]) return ;
  57. 	low[u] = disc[u] = dfsTime++;
  58. 	visited[u] = 1;
  59. 	FOR(i,0,sz(graph[u]))
  60. 	{
  61. 		int v = graph[u][i];
  62. 		if(v == par) continue;
  63.  
  64. 		if(!visited[v])
  65. 		{
  66. 			bridgeDFS(v, u);
  67. 			low[u] = min(low[u] , low[v]);
  68. 			if(low[v] > disc[u])
  69. 				isBridge[u][v] = isBridge[v][u] = 1;
  70. 		}
  71. 		else
  72. 			low[u] = min(low[u] , disc[v]);
  73. 	}
  74. }
  75.  
  76. int conversion[1010] = {0};
  77.  
  78. void findBridges()
  79. {
  80. 	FOR(i,0,1010) visited[i] = 0;
  81. 	bridgeDFS(1 , -1);
  82. 	FOR(i,0,1010) conversion[i] = i;
  83. }
  84.  
  85. vector< vector<PII> > bridgeGraph;
  86.  
  87. void bridgeTree()
  88. {
  89. 	FOR(i,0,1010) visited[i] = 0;
  90. 	FOR(ii,1,n+1)
  91. 	{
  92. 		if(visited[ii]) continue;
  93. 		queue<int> bfs;
  94. 		bfs.push(ii);
  95. 		visited[ii] = 1;
  96. 		while(!bfs.empty())
  97. 		{
  98. 			int ele = bfs.front();
  99. 			bfs.pop();
  100. 			FOR(i,0,sz(graph[ele]))
  101. 			{
  102. 				int v = graph[ele][i];
  103. 				if(isBridge[ele][v]) continue;
  104. 				if(visited[v] == 0)
  105. 				{
  106. 					conversion[v] = ii;
  107. 					visited[v] = 1;
  108. 					bfs.push(v);
  109. 				}
  110. 			}
  111. 		}
  112. 	}
  113. 	clr(bridgeGraph);
  114. 	bridgeGraph.resize(n + 1);
  115. 	FOR(i,1,n+1)
  116. 	{
  117. 		FOR(j,1,n+1)
  118. 		{
  119. 			if(isBridge[i][j])
  120. 			{
  121. 				int u = conversion[i];
  122. 				int v = conversion[j];
  123. 				bridgeGraph[u].pb(mp(v , f[i][j]));
  124. 				bridgeGraph[v].pb(mp(u , f[i][j]));
  125. 			}
  126. 		}
  127. 	}
  128. }
  129.  
  130. LL cost[1010][1010] = {{0}};
  131. LL shortestBridge[1010][1010] = {{0}};
  132.  
  133. void getans()
  134. {
  135. 	FOR(i,0,1010) FOR(j,0,1010) cost[i][j] = 0 ,shortestBridge[i][j] = INT_MAX;
  136. 	FOR(i,1,n+1) FOR(j,1,n+1)
  137. 	{
  138. 		int u = conversion[i];
  139. 		int v = conversion[j];
  140. 		if(u == v) cost[u][v] = cost[v][u] = 0;
  141. 		else cost[u][v] = cost[v][u] = max(cost[u][v] , f[i][j]);
  142. 	}
  143. 	FOR(i,1,n+1)
  144. 	{
  145. 		FOR(ii,0,1010) visited[ii] = 0;
  146. 		int u = conversion[i];
  147. 		if(visited[u]) continue;
  148. 		queue<PII> bfs;
  149. 		bfs.push(mp(u,INT_MAX));
  150.  
  151. 		visited[u] = 1;
  152. 		while(!bfs.empty())
  153. 		{
  154. 			PII ele = bfs.front();
  155. 			bfs.pop();
  156. 			u = ele.first;
  157. 			LL c = ele.second;
  158. 			FOR(ii,0,sz(bridgeGraph[u]))
  159. 			{
  160. 				PII q = bridgeGraph[u][ii];
  161. 				if(visited[q.first]) continue;
  162. 				visited[q.first] = 1;
  163. 				shortestBridge[conversion[i]][q.first] = shortestBridge[q.first][conversion[i]] = min(q.second , c);
  164. 				bfs.push(mp(q.first , min(q.second , c) ));
  165. 			}
  166. 		}
  167. 	}
  168. 	LL ans = 0;
  169. 	FOR(i,1,n+1)
  170. 	{
  171. 		FOR(j,1,n+1)
  172. 		{
  173. 			int u = conversion[i];
  174. 			int v = conversion[j];
  175. 			if(u == v) continue;
  176. 			ans = max(ans , cost[u][v] - shortestBridge[u][v]);
  177. 		}
  178. 	}
  179. 	cout << ans << endl;
  180. }
  181.  
  182. int main()
  183. {
  184. 	inp_s;
  185. 	DRT()
  186. 	{
  187. 		clr(low);
  188. 		clr(disc);
  189. 		clr(graph);
  190. 		dfsTime = 1;
  191.  
  192. 		cin >> n >> m >> mod;
  193. 		graph.resize(n + 1);
  194. 		FOR(i,0,1010) FOR(j,0,1010) isBridge[i][j] = 0, f[i][j] = -1;
  195. 		FOR(i,1,1010) FOR(j,1,1010) f[i][j] = preprocess(i,j);
  196. 		//step 1 : preprocess , done!
  197. 		FOR(i,0,m)
  198. 		{
  199. 			int a,b;
  200. 			cin >> a >> b;
  201. 			graph[a].pb(b);
  202. 			graph[b].pb(a);
  203. 		}
  204. 		low.resize(n + 1);
  205. 		disc.resize(n + 1);
  206. 		findBridges();
  207. 		//step 2 : finding bridges, done.
  208. 		bridgeTree();
  209. 		//step 3 : create the bridge tree, done.
  210. 		getans();
  211. 		//step 4 : this is what they need.. wonder why i couldnt make this step 1. 
  212. 	}
  213. 	return 0;
  214. }
Runtime error #stdin #stdout 0s 31328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mfu9PK
language:
C++ (gcc 8.3)
created:
8 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!