Submission #860363

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <functional>
#include <memory>
#include <cmath>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
 
template <class T>
struct persistent_array { // fully persistent
    static const int SHIFT_SIZE = 3; // log of the branching factor b
    // int size = 0; // the size n
    int shift = -1;
    // array<shared_ptr<persistent_array>, (1 << SHIFT_SIZE)> children; // smart pointers are slow...
    persistent_array *children[1 << SHIFT_SIZE] = {};
    T leaf = {};
    persistent_array(persistent_array const &) = default; // O(b)
    persistent_array() = default;
    persistent_array(int size) { // O(n \log_b n + m b \log_b n) for number of update m
        // size = a_size;
        if (size == 0) return;
        for (shift = 0; (1 << (shift * SHIFT_SIZE)) < size; ++ shift);
        shift = shift ? (shift - 1) * SHIFT_SIZE : -1;
    }
    inline T const & get(int i) const { // O(log_b n)
        return const_cast<persistent_array *>(this)->unsafe_get(i);
    }
    T & unsafe_get(int i) {
        if (shift == -1) return leaf;
        return children[index_high(i)]->unsafe_get(index_low(i));
    }
    T & set(int i) { // O(b log_b n), increment m
        if (shift == -1) return leaf;
        auto & p = children[index_high(i)];
        p = p ? new persistent_array(*p) : new persistent_array(child_size());
        return p->set(index_low(i));
    }
    inline int index_high(int index) const { return index >> shift; }
    inline int index_low (int index) const { return index & ((1 << shift) - 1); }
    inline int child_size()          const { return 1 << shift; }
    persistent_array deepcopy() const {
        persistent_array that;
        // that.size  = this->size;
        that.shift = this->shift;
        that.leaf  = this->leaf;
        repeat (i, 1 << SHIFT_SIZE) if (this->children[i]) that.children[i] = new persistent_array(this->children[i]->deepcopy());
        return that;
    }
};
 
struct persistent_disjoint_sets {
    persistent_array<int> xs;
    persistent_disjoint_sets() = default;
    explicit persistent_disjoint_sets(size_t n) : xs(n) { repeat (i,n) xs.set(i) = -1; }
    bool is_root(int i) { return xs.get(i) < 0; }
    int find_root(int i) { int j = xs.get(i); return j < 0 ? i : find_root(j); } // don't memoize
    // int find_root(int i) { return is_root(i) ? i : xs.set(i) = find_root(xs.get(i)); }
    int unsafe_find_root(int i) { return is_root(i) ? i : xs.unsafe_get(i) = find_root(xs.get(i)); }
    int set_size(int i) { return - xs.get(find_root(i)); }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            int *x_i = &xs.set(i);
            int *x_j = &xs.set(j);
            *x_i += *x_j;
            *x_j = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
    persistent_disjoint_sets deepcopy() {
        persistent_disjoint_sets that;
        that.xs = this->xs.deepcopy();
        return that;
    }
    inline int query(int x, int y) {
        x = find_root(x);
        y = find_root(y);
        return x == y ? set_size(x) : set_size(x) + set_size(y);
    };
};
 
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> a(m), b(m);
    repeat (e,m) {
        scanf("%d%d", &a[e], &b[e]);
        -- a[e]; -- b[e];
    }
    int q; scanf("%d", &q);
    vector<int> x(q), y(q), z(q);
    repeat (i,q) {
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
        -- x[i]; -- y[i];
    }
    // int n, m; cin >> n >> m;
    // vector<int> a(m), b(m);
    // repeat (e,m) {
    //     cin >> a[e] >> b[e];
    //     -- a[e]; -- b[e];
    // }
    // int q; cin >> q;
    // vector<int> x(q), y(q), z(q);
    // repeat (i,q) {
    //     cin >> x[i] >> y[i] >> z[i];
    //     -- x[i]; -- y[i];
    // }
    // prepare
    vector<persistent_disjoint_sets> t(m+1);
    t[0] = persistent_disjoint_sets(n);
    repeat (i,m) {
        t[i+1] = t[i];
        t[i+1].union_sets(a[i], b[i]);
        // if ((i+1) % (m / 12 + 1) == 0) {
        //     t[i+1] = t[i+1].deepcopy();
        //     repeat (j,n) {
        //         t[i+1].unsafe_find_root(j);
        //     }
        // }
    }
    // output
    repeat (i,q) {
        int low = -1, high = m;
        while (low + 1 < high) {
            int mid = (low + high) / 2;
            (t[mid].query(x[i], y[i]) < z[i] ? low : high) = mid;
        }
        cout << high << endl;
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d%d", &n, &m);
                                    ^
./Main.cpp:92:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[e], &b[e]);
                                    ^
./Main.cpp:95:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int q; scanf("%d", &q);
                           ^
./Main.cpp:98:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x[i], &y[i], &z[i]);
                                             ^

Judge Result