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){