• API
• FAQ
• Tools
• Archive
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);
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.
134.
135.   for (int i = 0; i < m; i++) {
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