Source code for submission s876

Go to diff to previous submission

ololo.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <memory.h>
  6. #include <cstring>
  7. #include <string>
  8.  
  9.  
  10. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  11. #define FI(i,b) FOR(i,0,b)
  12. #define V(t) vector < t >
  13. #define pb push_back
  14. #define MEMS(a,b) memset((a),(b),sizeof(a))
  15. #define U unsigned
  16. #define LL long long
  17. using namespace std;
  18.  
  19.  
  20. int n,m;
  21.  
  22. struct edge
  23. {
  24.   int u,v,l;
  25.   edge(){};
  26.   edge(int uu, int vv, int ll):u(uu),v(vv),l(ll){};
  27. };
  28.  
  29. bool comp(const edge& a, const edge& b)
  30. {
  31.   return a.l < b.l;
  32. }
  33.  
  34. edge e[1000100];
  35. int esz;
  36. V(V(int)) G;
  37.  
  38. int pr[1000100];
  39. int dsuinit(int n)
  40. {
  41.   FI(i,n) pr[i] =  i;
  42. }
  43.  
  44. int dsu_find(int v)
  45. {
  46.   if (pr[v] == v) return v;
  47.   return pr[v] = dsu_find(pr[v]);
  48. }
  49.  
  50. int dsu_unite(int u, int v)
  51. {
  52.   u = dsu_find(u);
  53.   v = dsu_find(v);
  54.   if (rand()%2) pr[u] = v;
  55.   else pr[v] = u;
  56. }
  57.  
  58.  
  59. int timIn[2222];
  60. int timOut[2222];
  61. const int maxD = 14;
  62. int par[2222][maxD];
  63. int rmq[2222][maxD];
  64. int was[10000100];
  65. int dfsTime = 0;
  66.  
  67. inline int gp(int v, int eNum)
  68. { if (v==e[eNum].v) return e[eNum].u; return e[eNum].v; }
  69.  
  70. const int root = 0;
  71.  
  72. void dfs(int v, int p = root, int l = 0)
  73. {
  74.   timIn[v]=++dfsTime;
  75.  
  76.   par[v][0] = p;
  77.   rmq[v][0] = l;
  78.  
  79.   FOR(i,1,maxD)
  80.   {
  81.     par[v][i] = par[ par[v][i-1] ][i-1];
  82.     rmq[v][i] = max( rmq[v][i-1] ,  rmq[ par[v][i-1] ][i-1] );
  83.   }  
  84.  
  85.   FI(i,G[v].size()) if (gp(v,G[v][i]) != p) dfs(gp(v,G[v][i]), v, e[G[v][i]].l);
  86.   timOut[v]=++dfsTime;
  87. }
  88.  
  89. inline int isParent(int u, int v) // is u parent v
  90. {
  91.   return (timIn[u] <= timIn[v] && timOut[u] >= timOut[v]);
  92. }
  93.  
  94. int getLCA(int u, int v)
  95. {
  96.   if (isParent(u,v)) return u;
  97.   if (isParent(v,u)) return v;
  98.   for (int i = maxD-1; i>=0; --i)
  99.   {
  100.     if (!isParent(par[u][i],v)) u = par[u][i];
  101.   }
  102.   return par[u][0];
  103. }
  104.  
  105. int getRMQ(int u, int lca)
  106. {
  107.   if (u == lca) return 0;
  108.   int res = 0;
  109.   for (int i = maxD-1; i>=0; --i)
  110.   {
  111.     if (!isParent(par[u][i],lca))
  112.     {
  113.       res = max(res,rmq[u][i]);
  114.       u = par[u][i]; 
  115.     }
  116.   }
  117.   return res = max(res, rmq[u][0]);
  118. }
  119.  
  120.  
  121. int getANS(int num)
  122. {
  123.   int u = e[num].u;
  124.   int v = e[num].v;
  125.   int lca = getLCA(u,v);
  126.   return e[num].l + max(getRMQ(u,lca), getRMQ(v,lca));
  127. }
  128.  
  129.  
  130.  
  131. int main()
  132. {
  133.   while (scanf("%d%d",&n,&m)!=EOF)
  134.   {
  135.     esz = 0;
  136.     G.clear();
  137.     G.resize(n);
  138.     FI(i,m)
  139.     {
  140.       int u,v,l;
  141.       scanf("%d%d%d",&u,&v,&l);
  142.       --u,--v;
  143.       e[esz++]=edge(u,v,l);
  144.     }
  145.     dsuinit(n);
  146.     sort(e,e+m,comp);
  147.     LL initTree = 0;
  148.     int initMax = 0;
  149.     LL best = 1000000000ll * 1000000000ll;
  150.     int edgeCnt = 0;
  151.     FI(i,m)
  152.     {
  153.       if (dsu_find(e[i].u)!=dsu_find(e[i].v))
  154.       {
  155. 	//cerr << e[i].u << ' ' << e[i].v << ' ' << e[i].l << endl;
  156. 	G[e[i].u].pb(i);
  157. 	G[e[i].v].pb(i);
  158. 	dsu_unite(e[i].u,e[i].v);
  159. 	initTree += e[i].l;
  160. 	initMax = max(initMax,e[i].l);
  161. 	edgeCnt++;
  162.       }
  163.     }
  164.     if (edgeCnt<n-1) {printf("disconnected\n"); continue;}
  165.  
  166.     best = min(best,initTree - 2*initMax);
  167.  
  168.     dfsTime = 0;
  169.     FI(i,n+1) timIn[i] = timOut[i] = 0;
  170.     dfs(root);
  171.  
  172.     FI(i,m) if (e[i].l > initMax) best = min(best, initTree - getANS(i));
  173.  
  174.     printf("%lld\n",best);
  175.  
  176.  
  177.   }
  178.  
  179.  
  180.  
  181.   return 0;
  182. }

Diff to submission s845

ololo.cpp

--- c4.s845.cteam050.spider.cpp.0.ololo.cpp
+++ c4.s876.cteam050.spider.cpp.0.ololo.cpp
@@ -111,6 +111,6 @@
     if (!isParent(par[u][i],lca))
     {
-      u = par[u][i]; 
       res = max(res,rmq[u][i]);
+      u = par[u][i]; 
     }
   }