Source code for submission s1334

Go to diff to previous submission

spider.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. using namespace std;
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. //////////////////////////////////
  29.  
  30. #define MAXN 1111111
  31. int N, M;
  32. int eA[MAXN], eB[MAXN], eC[MAXN], e[MAXN];
  33.  
  34. int father[MAXN], rank[MAXN];
  35.  
  36. int root(int v){
  37.   if(father[v] == -1) return v;
  38.   return (father[v] = root(father[v]));
  39. }
  40.  
  41. #define MAX 22222
  42. vector<int> graph[MAX], cost[MAX];
  43.  
  44. int T;
  45. int DFU(int edge){
  46.   int a = eA[edge], b = eB[edge], c = eC[edge];
  47.   int ca = root(a), cb = root(b);
  48.   //DEBUG(a); DEBUG(b); DEBUG(ca); DEBUG(cb);
  49.   if(ca == cb) return 0;
  50.   if(rank[ca] < rank[cb]) father[ca] = cb;
  51.   else if(rank[ca] > rank[cb]) father[cb] = ca;
  52.   else{
  53.     father[ca] = cb;
  54.     rank[cb]++;
  55.   }
  56.   graph[a].push_back(b);
  57.   graph[b].push_back(a);
  58.   cost[a].push_back(c);
  59.   cost[b].push_back(c);
  60.   T++;
  61.   return c;
  62. }
  63.  
  64. bool cmp(int a, int b){
  65.   return eC[a] < eC[b];
  66. }
  67.  
  68. int l[MAX][20], m[MAX][20], depth[MAX];
  69. void dfs(int v, int father, int d){
  70.   l[v][0] = father;
  71.   depth[v] = d;
  72.   REP(i, 19) l[v][i+1] = l[l[v][i]][i];
  73.   REP(i, 19) m[v][i+1] = min(m[v][i], m[l[v][i]][i]);
  74.   REP(i, graph[v].size()) if(graph[v][i] != father){
  75.     m[graph[v][i]][0] = cost[v][i];
  76.     dfs(graph[v][i], v, d+1);
  77.   }
  78. }
  79.  
  80. int up(int v, int d){
  81.   REP(i, 19) if(d & (1 << i)) v = l[v][i];
  82.   return v;
  83. }
  84.  
  85. int min_up(int v, int d){
  86.   int ans = INF; 
  87.   REP(i, 19) if(d & (1 << i)){ ans = min(ans, m[v][i]); v = l[v][i]; }
  88.   return ans;
  89. }
  90.  
  91. void build_tree(){
  92.   dfs(0, 0, 0);
  93. }
  94.  
  95. int lca(int a, int b){
  96.   FORD(i, 19, 0) if(l[a][i] != l[b][i]){ a = l[a][i]; b = l[b][i]; }
  97.   if(a != b) return l[a][0];
  98.   return a;
  99. }
  100.  
  101. int get(int a, int b){
  102.   if(depth[a] < depth[b]) swap(a, b);
  103.   int ans = min_up(a, depth[a] - depth[b]);
  104.   a = up(a, depth[a] - depth[b]);
  105.   int l = lca(a, b);
  106.   return min(ans, min(min_up(a, depth[a] - depth[l]), min_up(b, depth[b] - depth[l])));
  107. }
  108.  
  109. int main() {
  110.   while(scanf("%d%d", &N, &M) != EOF){
  111.     REP(i, M){
  112.       int a, b, c;
  113.       scanf("%d%d%d", &a, &b, &c);
  114.       a--; b--;
  115.       eA[i] = a;
  116.       eB[i] = b;
  117.       eC[i] = c;
  118. //      graph[a].push_back(b);
  119. //      graph[b].push_back(a);
  120.  
  121. //      cost[a].push_back(c);
  122. //      cost[b].push_back(c);
  123.       e[i] = i;
  124.     }
  125.     REP(i, N){
  126.       father[i] = -1;
  127.       rank[i] = 0;
  128.     }
  129.     sort(e, e + M, cmp);
  130.     int sum = 0;
  131.     T = 0;
  132.     REP(i, M) sum += DFU(e[i]);
  133.     //printf("used: %d\n", used);
  134.     if(T != N-1){ printf("disconnected\n"); continue; }
  135.     build_tree();
  136.     int ans = sum;
  137.     REP(i, M) ans = min(ans, sum - get(eA[i], eB[i]) - eC[i]);
  138.     printf("%d\n", ans);
  139.   }
  140.   return 0;
  141. }
  142.  

Diff to submission s1324

spider.cpp

--- c4.s1324.cteam002.spider.cpp.0.spider.cpp
+++ c4.s1334.cteam002.spider.cpp.0.spider.cpp
@@ -39,5 +39,5 @@
 }
 
-#define MAX 2222
+#define MAX 22222
 vector<int> graph[MAX], cost[MAX];
 
@@ -71,5 +71,5 @@
   depth[v] = d;
   REP(i, 19) l[v][i+1] = l[l[v][i]][i];
-  REP(i, 19) m[v][i+1] = min(m[v][i], m[m[v][i]][i]);
+  REP(i, 19) m[v][i+1] = min(m[v][i], m[l[v][i]][i]);
   REP(i, graph[v].size()) if(graph[v][i] != father){
     m[graph[v][i]][0] = cost[v][i];