zelleratumm

kek

Nov 15th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.23 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 100000 + 1;
  6.  
  7. typedef long long ll;
  8.  
  9. struct tree{
  10.  
  11.     size_t vertex_cnt = 0;
  12.  
  13.     size_t D = 0;
  14.  
  15.     size_t maxR = 0;
  16.     size_t minR = -1;
  17.     size_t dR;
  18.  
  19.     size_t *R = nullptr;
  20.     size_t *Rcnt = nullptr;
  21.     size_t *sRcnt = nullptr;
  22.  
  23.     ll *Rtot = nullptr;
  24.     ll *sRtot = nullptr;
  25.  
  26. };
  27.  
  28. struct vertex {
  29.  
  30.     size_t degree;
  31.     size_t radius = 0;
  32.     vertex **edges = nullptr;
  33.     tree *component = nullptr;
  34.  
  35. };
  36.  
  37. typedef tree* forest;
  38. typedef vertex* branch;
  39. typedef size_t* size_t_ptr;
  40. typedef ll* ll_t_ptr;
  41.  
  42. vertex *vertex_list;
  43.  
  44. void nullify_edges(vertex *leaf){
  45.  
  46.     assert(leaf);
  47.  
  48.     for (size_t i = 0; i < leaf->degree; ++i){
  49.         leaf->edges[i] = nullptr;
  50.     }
  51.  
  52. }
  53. void set_degree(vertex *leaf, size_t degree){
  54.  
  55.     assert(leaf);
  56.  
  57.     leaf->degree = degree;
  58.     leaf->edges = new branch[degree];
  59.     nullify_edges(leaf);
  60.  
  61. }
  62. void make_edge(vertex *a, size_t &a_cur_deg, vertex *b, size_t &b_cur_deg){
  63.  
  64.     assert(a);
  65.     assert(b);
  66.  
  67.     assert(a_cur_deg != a->degree && b_cur_deg != b->degree);
  68.  
  69.     a->edges[a_cur_deg++] = b;
  70.     b->edges[b_cur_deg++] = a;
  71.  
  72. }
  73.  
  74. void union_dfs(size_t &vertex_cnt, vertex *cur, vertex *prev = nullptr){
  75.  
  76.     ++vertex_cnt;
  77.     for (size_t i = 0; i < cur->degree; ++i){
  78.  
  79.         vertex *next = cur->edges[i];
  80.         if (next == prev){
  81.             continue;
  82.         }
  83.  
  84.         next->component = cur->component;
  85.         union_dfs(vertex_cnt, next, cur);
  86.  
  87.     }
  88.  
  89. }
  90.  
  91. vertex* calc_dfs(vertex *cur, vertex *prev = nullptr, size_t radius = 0){
  92.  
  93.     cur->radius = max(cur->radius, radius);
  94.  
  95.     vertex *best = nullptr;
  96.  
  97.     for (size_t i = 0; i < cur->degree; ++i){
  98.  
  99.         vertex *next = cur->edges[i];
  100.         if (next == prev){
  101.             continue;
  102.         }
  103.  
  104.         vertex *next_best = calc_dfs(next, cur, radius + 1);
  105.  
  106.         if (!best || next_best->radius > best->radius){
  107.             best = next_best;
  108.         }
  109.  
  110.     }
  111.  
  112.     if (best){
  113.         return best;
  114.     } else {
  115.         return cur;
  116.     }
  117.  
  118. }
  119.  
  120. void Rset_dfs(tree &seed, size_t &Rit, vertex *cur, vertex *prev = nullptr){
  121.  
  122.     assert(Rit != seed.vertex_cnt);
  123.  
  124.     seed.R[Rit++] = cur->radius;
  125.  
  126.     seed.maxR = max(seed.maxR, cur->radius);
  127.     seed.minR = min(seed.minR, cur->radius);
  128.  
  129.     for (size_t i = 0; i < cur->degree; ++i){
  130.  
  131.         vertex *next = cur->edges[i];
  132.  
  133.         if (next == prev){
  134.             continue;
  135.         }
  136.  
  137.         Rset_dfs(seed, Rit, next, cur);
  138.  
  139.     }
  140.  
  141. }
  142.  
  143. void make_tree(vertex *leaf){
  144.  
  145.     tree *seed = new tree;
  146.  
  147.     size_t &vertex_cnt = seed->vertex_cnt,
  148.            &D = seed->D,
  149.            &minR = seed->minR,
  150.            &maxR = seed->maxR,
  151.            &dR = seed->dR;
  152.  
  153.     size_t_ptr &R = seed->R,
  154.                &Rcnt = seed->Rcnt,
  155.                &sRcnt = seed->sRcnt;
  156.  
  157.     ll_t_ptr &Rtot = seed->Rtot,
  158.              &sRtot = seed->sRtot;
  159.  
  160.     leaf->component = seed;
  161.  
  162.     union_dfs(vertex_cnt, leaf);
  163.     calc_dfs(calc_dfs(calc_dfs(leaf)));
  164.  
  165.     R = new size_t[vertex_cnt];
  166.     size_t Rit = 0;
  167.     Rset_dfs(*seed, Rit, leaf);
  168.  
  169.     D = maxR;
  170.     dR = maxR - minR;
  171.  
  172.     sort(R, R + vertex_cnt);
  173.  
  174.     Rcnt = new size_t[dR + 1];
  175.     sRcnt = new size_t[dR + 1];
  176.     size_t str = 1, it = 0;
  177.     for (size_t i = 1; i < vertex_cnt; ++i){
  178.         if (R[i] == R[i - 1]){
  179.             ++str;
  180.         } else {
  181.             Rcnt[it] = str;
  182.             sRcnt[it] = it ? sRcnt[it - 1] + str : str;
  183.             ++it;
  184.             str = 1;
  185.         }
  186.     }
  187.  
  188.     Rcnt[it] = str;
  189.     sRcnt[it] = it ? sRcnt[it - 1] + str : str;
  190.  
  191.     Rtot = new ll[dR + 1];
  192.     sRtot = new ll[dR + 1];
  193.     for (size_t i = 0; i <= dR; ++i){
  194.         Rtot[i] = ll(minR + i) * ll(Rcnt[i]);
  195.         sRtot[i] = i ? sRtot[i - 1] + Rtot[i] : Rtot[i];
  196.     }
  197.  
  198. }
  199.  
  200. void make_forest(size_t vcnt, size_t ecnt, size_t *from, size_t *to){
  201.  
  202.     vertex_list = new vertex[vcnt];
  203.  
  204.     size_t degree[vcnt];
  205.     for (size_t i = 0; i < vcnt; ++i){
  206.         degree[i] = 0;
  207.     }
  208.  
  209.     for (size_t i = 0; i < ecnt; ++i){
  210.         ++degree[--from[i]];
  211.         ++degree[--to[i]];
  212.     }
  213.  
  214.     for (size_t i = 0; i < vcnt; ++i){
  215.         set_degree(vertex_list + i, degree[i]);
  216.         degree[i] = 0;
  217.     }
  218.  
  219.     for (size_t i = 0; i < ecnt; ++i){
  220.         make_edge(vertex_list + from[i], degree[from[i]], vertex_list + to[i], degree[to[i]]);
  221.     }
  222.  
  223.     for (size_t i = 0; i < vcnt; ++i){
  224.         if (!vertex_list[i].component){
  225.             make_tree(vertex_list + i);
  226.         }
  227.     }
  228.  
  229. }
  230.  
  231. typedef long double ld;
  232.  
  233. map < pair < tree*, tree* >, ld > cash;
  234.  
  235. void calcD(size_t x, size_t y){
  236.  
  237.     tree *a = vertex_list[--x].component,
  238.          *b = vertex_list[--y].component;
  239.  
  240.     if (a == b){
  241.         puts("-1");
  242.         return;
  243.     }
  244.  
  245.     pair < tree*, tree* > pos = make_pair(a, b);
  246.  
  247.     if (cash.count(pos)){
  248.         printf("%.10f\n", double(cash[pos]));
  249.         return;
  250.     }
  251.  
  252.     ll tot = ll(a->vertex_cnt) * ll(b->vertex_cnt);
  253.  
  254.     size_t limD = max(a->D, b->D);
  255.     ll result = (ll(a->sRtot[a->dR]) * ll(b->sRcnt[b->dR]))
  256.               + (ll(a->sRcnt[a->dR]) * ll(b->sRtot[b->dR]))
  257.               + (ll(a->sRcnt[a->dR]) * ll(b->sRcnt[b->dR]));
  258.  
  259.     int scnt = limD - a->minR - b->minR;
  260.     if (scnt < 1){
  261.         printf("%.10f\n", double(cash[pos] = (result / ld(tot))));
  262.         return;
  263.     }
  264.  
  265.     if (a->dR > b->dR){
  266.         swap(a, b);
  267.     }
  268.  
  269.     size_t lim = min(a->dR + 1, size_t(scnt - 1));
  270.     for (int i = 1; i <= lim; ++i){
  271.  
  272.         int x = i - 1,
  273.             y = scnt - i - 1;
  274.  
  275.         if (b->dR < y){
  276.             continue;
  277.         }
  278.  
  279.         result -= (ll(a->Rcnt[x]) * b->sRtot[y] + a->Rtot[x] * ll(b->sRcnt[y]) + ll(a->Rcnt[x]) * ll(b->sRcnt[y]));
  280.         result += (ll(a->Rcnt[x]) * ll(b->sRcnt[y]) * ll(limD));
  281.  
  282.     }
  283.  
  284.     printf("%.10f\n", double(cash[pos] = (result / ld(tot))));
  285.  
  286. }
  287.  
  288. int main(){
  289.  
  290.     size_t n, m, q;
  291.     cin >> n >> m >> q;
  292.  
  293.     size_t *from = new size_t[m],
  294.            *to = new size_t[m];
  295.     for (size_t i = 0; i < m; ++i){
  296.         cin >> from[i] >> to[i];
  297.     }
  298.  
  299.     make_forest(n, m, from, to);
  300.  
  301.     for (size_t i = 0; i < q; ++i){
  302.  
  303.         size_t a, b;
  304.         cin >> a >> b;
  305.  
  306.         calcD(a, b);
  307.  
  308.     }
  309.  
  310. }
Add Comment
Please, Sign In to add comment