Source code for submission s1067

Go to diff to previous submission

spider.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cctype>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <algorithm>
  9. #include <deque>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <vector>
  16.  
  17. #define FOR(I,A,B)	for(int I = (A); I < (B); ++I)
  18.  
  19. // #define INF (int)2e9
  20. #define EPS 1e-9
  21. #define PI 3.14159265358979
  22.  
  23. using namespace std;
  24.  
  25. typedef pair<int, int> ii;
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28.  
  29. #define MAXN 2100
  30. #define MAXM 1100000
  31. #define LOGMAXN 50
  32.  
  33. struct Vrchol{
  34. 	Vrchol* parent;
  35. 	int rank;
  36. };
  37. struct Hrana{
  38. 	int z, d, cena;
  39. 	bool operator<(const Hrana&h)const{
  40. 		return cena<h.cena;
  41. 	}
  42. };
  43.  
  44. Vrchol* root(Vrchol*v){
  45. 	Vrchol* r = v;
  46. 	while(r->parent!=0)
  47. 		r = r->parent;
  48. 	while(v!=r){
  49. 		Vrchol*n=v->parent;
  50. 		v->parent = r;
  51. 		v = n;
  52. 	}
  53. 	return r;
  54. }
  55.  
  56. bool join(Vrchol* a, Vrchol* b){
  57. 	a=root(a);
  58. 	b=root(b);
  59. 	if(a==b)
  60. 		return false;
  61. 	else{
  62. 		if(a->rank>b->rank)
  63. 			b->parent=a;
  64. 		else if(a->rank<b->rank)
  65. 			a->parent = b;
  66. 		else
  67. 			b->parent = a, a->rank++;
  68. 	}
  69. 	return true;
  70. }
  71.  
  72. int N, M;
  73. vector<int> tree[MAXN];
  74. vector<int> ceny[MAXN];
  75. int sum;
  76. int nejd;
  77. int T[MAXN];
  78. int L[MAXN];
  79. int P[MAXN][LOGMAXN];
  80. int E[MAXN];
  81. int H[MAXN][LOGMAXN];
  82. int X;
  83.  
  84. void dfs(int v, int p, int e, int l) {
  85. 	T[v] = p;
  86. 	L[v] = l;
  87. 	E[v] = e;
  88. 	FOR (i, 0, tree[v].size()) {
  89. 		if (tree[v][i]!=p)
  90. 			dfs(tree[v][i], v, ceny[v][i], l+1);
  91. 	}
  92. }
  93.  
  94. void process() {
  95. 	int i, j;
  96. 	for (i=0; i<N; i++)
  97. 		for (j=0; 1<<j<N; j++) {
  98. 			P[i][j] = -1;
  99. 			H[i][j] = 0;
  100. 		}
  101. 	for (i=0; i<N; i++) {
  102. 		P[i][0] = T[i];
  103. 		H[i][0] = E[i];
  104. 	}
  105. 	for (j=1; 1<<j < N; j++)
  106. 		for (i=0; i<N; i++)
  107. 			if (P[i][j-1]!=-1) {
  108. 				P[i][j] = P[P[i][j-1]][j-1];
  109. 				H[i][j] = max(H[i][j-1], H[P[i][j-1]][j-1]);
  110. 			}
  111. }
  112.  
  113. int query(int p, int q) {
  114. 	int lo, i;
  115. 	int ret = 0;
  116. 	if (L[p] < L[q]) {
  117. 		swap(p, q);
  118. 	}
  119. 	for (lo=1; 1<<lo <=L[p]; lo++);
  120. 	lo--;
  121. 	for (i=lo; i>=0; i--)
  122. 		if (L[p] - (1<<i) >=L[q]) {
  123. 			ret = H[p][i];
  124. 			p = P[p][i];
  125. 		}
  126. 	if (p==q)
  127. 		return ret;
  128. 	for (i=lo; i>=0; i--)
  129. 		if (P[p][i] != -1 && P[p][i] != P[q][i]) {
  130. 			ret = max(ret, H[p][i]);
  131. 			ret = max(ret, H[q][i]);
  132. 			p = P[p][i];
  133. 			q = P[q][i];
  134. 		}
  135. 	return max(ret, max(E[p], E[q]));
  136. }
  137.  
  138. Hrana hrany[MAXM];
  139. Vrchol vrcholy[MAXN];
  140.  
  141. bool solve() {
  142. 		X=0;
  143. 		if (scanf("%d%d",&N,&M)<0) return false;
  144. 		for(int i=0;i<N;++i){
  145. 			vrcholy[i].rank= 0;
  146. 			vrcholy[i].parent= 0;
  147. 			tree[i].clear(); ceny[i].clear();
  148. 		}
  149. 		for(int i=0;i<M;++i){
  150. 			scanf("%d%d%d",&hrany[i].z,&hrany[i].d,&hrany[i].cena);
  151. 			hrany[i].z--, hrany[i].d--;
  152. 		}
  153. 		sort(hrany, hrany+M);
  154. 		sum = 0;
  155. 		nejd = 0;
  156. 		for(int i=0;i<M;++i){
  157. 			if(join(vrcholy+hrany[i].z, vrcholy+hrany[i].d)){
  158. 				tree[hrany[i].z].push_back(hrany[i].d);
  159. 				ceny[hrany[i].z].push_back(hrany[i].cena);
  160. 				tree[hrany[i].d].push_back(hrany[i].z);
  161. 				ceny[hrany[i].d].push_back(hrany[i].cena);
  162. 				sum+=hrany[i].cena;
  163. 				nejd = max(nejd, hrany[i].cena);
  164. 				X++;
  165. 			}
  166. 		}
  167.  
  168. 		if (X<N-1) {
  169. 			printf("disconnected\n");
  170. 			return true;
  171. 		}
  172. 		dfs(0, -1, 0, 0);
  173. 		process();
  174. 		int ret = INT_MAX;
  175. 		FOR (i, 0, M) {
  176. 			ret = min(ret, sum-query(hrany[i].z, hrany[i].d)-hrany[i].cena);
  177. 		}
  178. 		printf("%d\n", ret);
  179. 		return true;
  180. }
  181.  
  182. int main() {
  183. 		while(solve());
  184. 		return 0;
  185. }

Diff to submission s1040

spider.cpp

--- c4.s1040.cteam014.spider.cpp.0.spider.cpp
+++ c4.s1067.cteam014.spider.cpp.0.spider.cpp
@@ -29,5 +29,5 @@
 #define MAXN 2100
 #define MAXM 1100000
-#define LOGMAXN 20
+#define LOGMAXN 50
 
 struct Vrchol{
@@ -145,4 +145,5 @@
                         vrcholy[i].rank= 0;
                         vrcholy[i].parent= 0;
+                        tree[i].clear(); ceny[i].clear();
                 }
                 for(int i=0;i<M;++i){