Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- using namespace std;
- #define null NULL
- namespace persistent_segment_tree {
- struct node {
- int tl, tr, x;
- node *l, *r;
- node() { l = r = 0; tl = tr = x = 0; }
- node(node *l, node *r, int tl, int tr, int x) {
- this->l = l; this->r = r;
- this->tl = tl; this->tr = tr;
- this->x = x;
- }
- };
- void build(node *v, int tl, int tr) {
- v->tl = tl;
- v->tr = tr;
- if (tl != tr) {
- int m = (tl + tr) / 2;
- v->l = new node;
- v->r = new node;
- build(v->l, tl, m);
- build(v->r, m + 1, tr);
- }
- }
- node *set(node *v, int i, int x) {
- if (v->tl == v->tr)
- return new node(null, null, v->tl, v->tr, x);
- int m = (v->tl + v->tr) / 2;
- if (i <= m)
- return new node(set(v->l, i, x), v->r, v->tl, v->tr, x);
- else return new node(v->l, set(v->r, i, x), v->tl, v->tr, x);
- }
- int get(node *v, int l, int r) {
- if (v->tl == l && v->tr == r)
- return v->x;
- int m = (v->tl + v->tr) / 2;
- if (r <= m)
- return get(v->l, l, r);
- if (l > m)
- return get(v->r, l, r);
- return get(v->l, l, m) + get(v->r, m + 1, r);
- }
- }
- namespace persistent_dsu {
- namespace pst = persistent_segment_tree;
- typedef pst::node pst_node;
- // We describe state of DSU with an array of parents and their ranks
- struct state {
- pst_node *parents;
- pst_node *ranks;
- state() { parents = ranks = null; }
- state(pst_node *parents, pst_node *ranks) {
- this->parents = parents;
- this->ranks = ranks;
- }
- };
- state * build(int size) {
- pst_node *parents = new pst_node();
- pst_node *ranks = new pst_node();
- pst::build(parents, 0, size - 1);
- pst::build(ranks, 0, size - 1);
- for (int i = 0; i < size; i++)
- parents = pst::set(parents, i, i);
- return new state(parents, ranks);
- }
- // This implementation doesn't use path compression to avoid creating too many
- // nodes in persistent segment trees
- int find(state *st, int x) {
- int direct_parent = pst::get(st->parents, x, x);
- return direct_parent == x ? x : find(st, direct_parent);
- }
- state * unite(state *st, int x, int y) {
- st = new state(st->parents, st->ranks);
- x = find(st, x);
- y = find(st, y);
- int xRank = pst::get(st->ranks, x, x);
- int yRank = pst::get(st->ranks, y, y);
- if (xRank > yRank) {
- st->parents = pst::set(st->parents, y, x);
- st->ranks = pst::set(st->ranks, x, xRank + yRank);
- } else {
- st->parents = pst::set(st->parents, x, y);
- st->ranks = pst::set(st->ranks, y, xRank + yRank);
- }
- return st;
- }
- }
- int main() {
- typedef persistent_dsu::state pd_state;
- namespace pd = persistent_dsu;
- int n, m, q;
- scanf("%d%d%d", &n, &m, &q);
- vector<pair<int, pair<int, int> > > roads;
- for (int i = 0; i < m; i++) {
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- roads.push_back(make_pair(c, make_pair(a, b)));
- }
- vector<pair<int, int> > queries;
- for (int i = 0; i < q; i++) {
- int a, b;
- scanf("%d%d", &a, &b);
- queries.push_back(make_pair(a, b));
- }
- pd_state *state = pd::build(n);
- vector<pd_state*> states;
- sort(roads.begin(), roads.end());
- for (int i = 0; i < m; i++) {
- int a = roads[i].second.first;
- int b = roads[i].second.second;
- if (pd::find(state, a) != pd::find(state, b)) {
- state = pd::unite(state, a, b);
- }
- states.push_back(state);
- }
- for (int i = 0; i < q; i++) {
- int a = queries[i].first;
- int b = queries[i].second;
- int l = -1, r = m, mid;
- while (r - l > 1) {
- mid = (l + r) / 2;
- if (pd::find(states[mid], a) == pd::find(states[mid], b))
- r = mid;
- else
- l = mid;
- }
- // r - first time when a and b come into same component
- printf("%d\n", roads[r].first);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement