fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <string>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <stack>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. #include <functional>
  13. #include <numeric>
  14. #include <cstdlib>
  15. #include <iomanip>
  16. #include <cassert>
  17.  
  18. using namespace std;
  19.  
  20. const int MAXN = 200005;
  21. const int LOG = 18;
  22.  
  23. int center, timer, n, m, l, x, y, t, edgesInPath, furthestNode, diameterNode1, diameterNode2;
  24. long long maxDist;
  25. int timeIn[MAXN];
  26. int timeOut[MAXN];
  27. int up[MAXN][19];
  28. bool visited[MAXN];
  29. int edgesFromRoot[MAXN];
  30. long long distanceFromRoot[MAXN];
  31. vector<pair<int, int> > graph[MAXN];
  32. long long componentDiameter, centerFar;
  33.  
  34. void dfsInit(int v, int parent, int pathEdges, long long pathLength) {
  35. 	visited[v] = true;
  36. 	up[v][0] = parent;
  37. 	distanceFromRoot[v] = pathLength;
  38. 	edgesFromRoot[v] = pathEdges;
  39. 	timeIn[v] = ++timer;
  40. 	for (int i = 1; i <= LOG; i++) {
  41. 		up[v][i] = up[up[v][i - 1]][i - 1];
  42. 	}
  43. 	for (int i = 0; i < (int)graph[v].size(); i++) {
  44. 		int to = graph[v][i].first;
  45. 		int len = graph[v][i].second;
  46. 		if (to != parent) {
  47. 			dfsInit(to, v, pathEdges + 1, pathLength + len);
  48. 		}
  49. 	}
  50. 	timeOut[v] = ++timer;
  51. }
  52.  
  53. void dfsDiameter(int v, int parent, int pathEdges, long long pathLength) {
  54. 	if (pathLength > maxDist) {
  55. 		maxDist = pathLength;
  56. 		furthestNode = v;
  57. 		edgesInPath = pathEdges;
  58. 	}
  59. 	for (int i = 0; i < (int)graph[v].size(); i++) {
  60. 		int to = graph[v][i].first;
  61. 		int len = graph[v][i].second;
  62. 		if (to != parent) {
  63. 			dfsDiameter(to, v, pathEdges + 1, pathLength + len);
  64. 		}
  65. 	}
  66. }
  67.  
  68. struct component {
  69. 	long long diameter;
  70. 	int center;
  71. 	long long centerFar;
  72. 	component() {}
  73. 	component(long long _diameter, int _center, long long _centerFar): diameter(_diameter), center(_center), centerFar(_centerFar) {}
  74. };
  75.  
  76. inline bool operator < (const component & a, const component & b) {
  77. 	return (a.diameter > b.diameter || (a.diameter == b.diameter && a.center < b.center));
  78. }
  79.  
  80. vector<component> initialComponents;
  81. multiset<component> forest;
  82. multiset<component>::iterator it;
  83. component componentA, componentB;
  84.  
  85. bool isAncestor(int x, int y) {
  86. 	return (timeIn[x] <= timeIn[y] && timeOut[x] >= timeOut[y]);
  87. }
  88.  
  89. int findLCA(int a, int b) {
  90. 	if (isAncestor(a, b)) {
  91. 		return a;
  92. 	}
  93. 	if (isAncestor(b, a)) {
  94. 		return b;
  95. 	}
  96. 	for (int i = LOG; i >= 0; i--) {
  97. 		if (!isAncestor(up[a][i], b)) {
  98. 			a = up[a][i];
  99. 		}
  100. 	}
  101. 	return up[a][0];
  102. }
  103.  
  104. long long distanceBetween(int a, int b) {
  105. 	return distanceFromRoot[a] + distanceFromRoot[b] - 2 * distanceFromRoot[findLCA(a, b)];
  106. }
  107.  
  108. int edgesBetween(int a, int b) {
  109. 	return edgesFromRoot[a] + edgesFromRoot[b] - 2 * edgesFromRoot[findLCA(a, b)];
  110. }
  111.  
  112. int getUp(int v, int jump) {
  113. 	for (int i = 0; i <= LOG; i++) {
  114. 		if (jump & (1 << i)) {
  115. 			v = up[v][i];
  116. 		}
  117. 	}
  118. 	return v;
  119. }
  120.  
  121. int pathDive(int pathNode1, int pathNode2, int edgesInPath, int dive) {
  122. 	int LCA = findLCA(pathNode1, pathNode2);
  123. 	int jump = min(dive, edgesFromRoot[pathNode1] - edgesFromRoot[LCA]);
  124. 	dive -= jump;
  125. 	if (dive > 0) {
  126. 		return getUp(pathNode2, edgesFromRoot[pathNode2] - edgesFromRoot[LCA] - dive);
  127. 	} else {
  128. 		return getUp(pathNode1, jump);
  129. 	}
  130. }
  131.  
  132. int findCenter(int pathNode1, int pathNode2, int edgesInPath) {
  133. 	int l, r, mid, iter, pathNode, bestCenter;
  134. 	long long f1, f2, bestF;
  135. 	bestF = (long long)9e18;
  136. 	l = 0; r = edgesInPath;
  137. 	for (iter = 0; iter < LOG; iter++) {
  138. 		mid = (l + r) >> 1;
  139. 		pathNode = pathDive(pathNode1, pathNode2, edgesInPath, mid);
  140. 		f1 = max(distanceBetween(pathNode, pathNode1), distanceBetween(pathNode, pathNode2));
  141. 		if (f1 < bestF) {
  142. 			bestF = f1;
  143. 			bestCenter = pathNode;
  144. 		}
  145. 		if (mid < edgesInPath) {
  146. 			pathNode = pathDive(pathNode1, pathNode2, edgesInPath, mid + 1);
  147. 			f2 = max(distanceBetween(pathNode, pathNode1), distanceBetween(pathNode, pathNode2));
  148. 			if (f2 < bestF) {
  149. 				bestF = f2;
  150. 				bestCenter = pathNode;
  151. 			}
  152. 			if (f1 < f2) {
  153. 				r = mid;
  154. 			} else {
  155. 				l = mid;
  156. 			}
  157. 		}
  158. 	}
  159. 	for (int goBack = 1; goBack <= 4; goBack++) {
  160. 		if (edgesBetween(pathNode1, bestCenter) < goBack) {
  161. 			break;
  162. 		}
  163. 		int attempt = pathDive(bestCenter, pathNode1, edgesBetween(pathNode1, bestCenter), goBack);
  164. 		f1 = max(distanceBetween(pathNode1, attempt), distanceBetween(pathNode2, attempt));
  165. 		if (f1 < bestF) {
  166. 			bestF = f1;
  167. 			bestCenter = attempt;
  168. 		}
  169. 	}
  170. 	for (int goForward = 1; goForward <= 4; goForward++) {
  171. 		if (edgesBetween(bestCenter, pathNode2) < goForward) {
  172. 			break;
  173. 		}
  174. 		int attempt = pathDive(bestCenter, pathNode2, edgesBetween(bestCenter, pathNode2), goForward);
  175. 		f1 = max(distanceBetween(pathNode1, attempt), distanceBetween(pathNode2, attempt));
  176. 		if (f1 < bestF) {
  177. 			bestF = f1;
  178. 			bestCenter = attempt;
  179. 		}
  180. 	}
  181. 	return bestCenter;
  182. }
  183.  
  184. component mergeComponents(component a, component b) {
  185. 	int aCenter = a.center;
  186. 	int bCenter = b.center;
  187. 	long long aFar = a.centerFar;
  188. 	long long bFar = b.centerFar;
  189. 	long long cDiameter = aFar + l + bFar;
  190. 	int cCenter;
  191. 	long long cCenterFar;
  192. 	if (aFar <= bFar) {
  193. 		cCenter = bCenter;
  194. 		cCenterFar = max(aFar + l, bFar);
  195. 	} else {
  196. 		cCenter = aCenter;
  197. 		cCenterFar = max(aFar, bFar + l);
  198. 	}
  199. 	if (cDiameter < a.diameter) {
  200. 		cDiameter = a.diameter;
  201. 		cCenter = a.center;
  202. 		cCenterFar = a.centerFar;
  203. 	} 
  204. 	if (cDiameter < b.diameter) {
  205. 		cDiameter = b.diameter;
  206. 		cCenter = b.center;
  207. 		cCenterFar = b.centerFar;
  208. 	}
  209. 	return component(cDiameter, cCenter, cCenterFar);
  210. }
  211.  
  212. int main() {
  213. 	//freopen("input.txt", "r", stdin);
  214. 	scanf("%d %d %d", &n, &m, &l);
  215. 	for (int i = 0; i < m; i++) {
  216. 		scanf("%d %d %d", &x, &y, &t);
  217. 		graph[x].push_back(make_pair(y, t));
  218. 		graph[y].push_back(make_pair(x, t));
  219. 	}
  220. 	for (int i = 0; i < n; i++) {
  221. 		if (visited[i]) {
  222. 			continue;
  223. 		}
  224. 		dfsInit(i, i, 0, 0);
  225. 		maxDist = furthestNode = -1;
  226. 		dfsDiameter(i, i, 0, 0);
  227. 		diameterNode1 = furthestNode;
  228. 		maxDist = furthestNode = -1;
  229. 		dfsDiameter(diameterNode1, diameterNode1, 0, 0);
  230. 		diameterNode2 = furthestNode;
  231. 		assert(diameterNode1 != -1 && diameterNode2 != -1);
  232. 		center = findCenter(diameterNode1, diameterNode2, edgesInPath);
  233. 		componentDiameter = maxDist;
  234. 		centerFar = max(distanceBetween(diameterNode1, center), distanceBetween(diameterNode2, center));
  235. 		initialComponents.push_back(component(componentDiameter, center, centerFar));
  236. 	}
  237. 	sort(initialComponents.begin(), initialComponents.end());
  238. 	component ans = initialComponents[0];
  239. 	for (int i = 1; i < (int)initialComponents.size(); i++) {
  240. 		ans = mergeComponents(ans, initialComponents[i]);
  241. 	}
  242. 	cout << ans.diameter << "\n";
  243. 	return 0;
  244. }
Runtime error #stdin #stdout 0s 24392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hfqY9m
language:
C++14 (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!