SHARE
TWEET

Untitled

a guest Jun 15th, 2013 150 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. #define null NULL
  7.  
  8. namespace persistent_segment_tree {
  9.   struct node {
  10.     int tl, tr, x;
  11.     node *l, *r;
  12.     node() { l = r = 0; tl = tr = x = 0; }
  13.     node(node *l, node *r, int tl, int tr, int x) {
  14.       this->l = l; this->r = r;
  15.       this->tl = tl; this->tr = tr;
  16.       this->x = x;
  17.     }
  18.   };
  19.  
  20.   void build(node *v, int tl, int tr) {
  21.     v->tl = tl;
  22.     v->tr = tr;
  23.     if (tl != tr) {
  24.       int m = (tl + tr) / 2;
  25.       v->l = new node;
  26.       v->r = new node;
  27.       build(v->l, tl, m);
  28.       build(v->r, m + 1, tr);
  29.     }
  30.   }
  31.  
  32.   node *set(node *v, int i, int x) {
  33.     if (v->tl == v->tr)
  34.       return new node(null, null, v->tl, v->tr, x);
  35.     int m = (v->tl + v->tr) / 2;
  36.     if (i <= m)
  37.       return new node(set(v->l, i, x), v->r, v->tl, v->tr, x);
  38.     else return new node(v->l, set(v->r, i, x), v->tl, v->tr, x);
  39.   }
  40.  
  41.   int get(node *v, int l, int r) {
  42.     if (v->tl == l && v->tr == r)
  43.       return v->x;
  44.     int m = (v->tl + v->tr) / 2;
  45.     if (r <= m)
  46.       return get(v->l, l, r);
  47.     if (l > m)
  48.       return get(v->r, l, r);
  49.     return get(v->l, l, m) + get(v->r, m + 1, r);
  50.   }
  51. }
  52.  
  53. namespace persistent_dsu {
  54.   namespace pst = persistent_segment_tree;
  55.   typedef pst::node pst_node;
  56.  
  57.   // We describe state of DSU with an array of parents and their ranks
  58.   struct state {
  59.     pst_node *parents;
  60.     pst_node *ranks;
  61.  
  62.     state() { parents = ranks = null; }
  63.     state(pst_node *parents, pst_node *ranks) {
  64.       this->parents = parents;
  65.       this->ranks = ranks;
  66.     }
  67.   };
  68.  
  69.   state * build(int size) {
  70.     pst_node *parents = new pst_node();
  71.     pst_node *ranks = new pst_node();
  72.     pst::build(parents, 0, size - 1);
  73.     pst::build(ranks, 0, size - 1);
  74.  
  75.     for (int i = 0; i < size; i++)
  76.       parents = pst::set(parents, i, i);
  77.  
  78.     return new state(parents, ranks);
  79.   }
  80.  
  81.   // This implementation doesn't use path compression to avoid creating too many
  82.   // nodes in persistent segment trees
  83.   int find(state *st, int x) {
  84.     int direct_parent = pst::get(st->parents, x, x);
  85.     return direct_parent == x ? x : find(st, direct_parent);
  86.   }
  87.  
  88.   state * unite(state *st, int x, int y) {
  89.     st = new state(st->parents, st->ranks);
  90.  
  91.     x = find(st, x);
  92.     y = find(st, y);
  93.  
  94.     int xRank = pst::get(st->ranks, x, x);
  95.     int yRank = pst::get(st->ranks, y, y);
  96.     if (xRank > yRank) {
  97.       st->parents = pst::set(st->parents, y, x);
  98.       st->ranks = pst::set(st->ranks, x, xRank + yRank);
  99.     } else {
  100.       st->parents = pst::set(st->parents, x, y);
  101.       st->ranks = pst::set(st->ranks, y, xRank + yRank);
  102.     }
  103.  
  104.     return st;
  105.   }
  106. }
  107.  
  108. int main() {
  109.   typedef persistent_dsu::state pd_state;
  110.   namespace pd = persistent_dsu;
  111.  
  112.   int n, m, q;
  113.   scanf("%d%d%d", &n, &m, &q);
  114.  
  115.   vector<pair<int, pair<int, int> > > roads;
  116.   for (int i = 0; i < m; i++) {
  117.     int a, b, c;
  118.     scanf("%d%d%d", &a, &b, &c);
  119.     roads.push_back(make_pair(c, make_pair(a, b)));
  120.   }
  121.  
  122.   vector<pair<int, int> > queries;
  123.   for (int i = 0; i < q; i++) {
  124.     int a, b;
  125.     scanf("%d%d", &a, &b);
  126.     queries.push_back(make_pair(a, b));
  127.   }
  128.  
  129.  
  130.   pd_state *state = pd::build(n);
  131.   vector<pd_state*> states;
  132.  
  133.   sort(roads.begin(), roads.end());
  134.  
  135.   for (int i = 0; i < m; i++) {
  136.     int a = roads[i].second.first;
  137.     int b = roads[i].second.second;
  138.     if (pd::find(state, a) != pd::find(state, b)) {
  139.       state = pd::unite(state, a, b);
  140.     }
  141.  
  142.     states.push_back(state);
  143.   }
  144.  
  145.   for (int i = 0; i < q; i++) {
  146.     int a = queries[i].first;
  147.     int b = queries[i].second;
  148.  
  149.     int l = -1, r = m, mid;
  150.  
  151.     while (r - l > 1) {
  152.       mid = (l + r) / 2;
  153.       if (pd::find(states[mid], a) == pd::find(states[mid], b))
  154.         r = mid;
  155.       else
  156.         l = mid;
  157.     }
  158.  
  159.     // r - first time when a and b come into same component
  160.     printf("%d\n", roads[r].first);
  161.   }
  162.  
  163.   return 0;
  164. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top