Submission #19550879


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <random>
using namespace std; typedef unsigned long long _ulong; typedef int lint; typedef pair<lint, lint> plint; typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;++i)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;--i)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
#define fi first
#define se second
struct fast_ios { fast_ios() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
template<class T> auto add = [](T a, T b) -> T { return a + b; };
template<class T> auto f_max = [](T a, T b) -> T { return max(a, b); };
template<class T> auto f_min = [](T a, T b) -> T { return min(a, b); };
template<class T> using V = vector<T>;
using Vl = V<lint>; using VVl = V<Vl>;
template< typename T > ostream& operator<<(ostream& os, const vector< T >& v) {
	for (int i = 0; i < (int)v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : "");
	return os;
}
template< typename T >istream& operator>>(istream& is, vector< T >& v) {
	for (T& in : v) is >> in;
	return is;
}
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
lint gcd(lint a, lint b) { if (b == 0) return a; else return gcd(b, a % b); }
lint ceil(lint a, lint b) { return (a + b - 1) / b; }
lint digit(lint a) { return (lint)log10(a); }
lint e_dist(plint a, plint b) { return abs(a.fi - b.fi) * abs(a.fi - b.fi) + abs(a.se - b.se) * abs(a.se - b.se); }
lint m_dist(plint a, plint b) { return abs(a.fi - b.fi) + abs(a.se - b.se); }
void Worshall_Floyd(VVl& g) { REP(k, SZ(g)) REP(i, SZ(g)) REP(j, SZ(g)) chmin(g[i][j], g[i][k] + g[k][j]); }
const lint MOD = 998244353, INF = 1e9 + 1;
lint dx[8] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
bool YN(bool flag) { cout << (flag ? "YES" : "NO") << endk; return flag; } bool yn(bool flag) { cout << (flag ? "Yes" : "No") << endk; return flag; }
struct Edge {
	lint from, to;
	lint cost;
	Edge(lint u, lint v, lint c) {
		cost = c;
		from = u;
		to = v;
	}
	bool operator<(const Edge& e) const {
		return cost < e.cost;
	}
};
struct WeightedEdge {
	lint to;
	lint cost;
	WeightedEdge(lint v, lint c = 1) {
		to = v;
		cost = c;
	}
	bool operator<(const WeightedEdge& e) const {
		return cost < e.cost;
	}
};
using WeightedGraph = V<V<WeightedEdge>>;
typedef pair<lint, plint> tlint;
typedef pair<plint, plint> qlint;
typedef pair<string, lint> valstring;

struct UnionFind {
public:
    UnionFind() : _n(0) {}
    UnionFind(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        if (used_count) {
            if (count_in_set[x].size() < count_in_set[y].size()) {
                std::swap(count_in_set[x], count_in_set[y]);
            }
            for (auto p : count_in_set[y]) {
                count_in_set[x][p.first] += p.second;
            }
        }
        if (set_operate) {
            root_values[x] = f(root_values[y], root_values[x]);
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;

        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }
    //update root calc
    //set by set operations
    void set_operate_and_value(std::vector<lint> array, function<lint(lint, lint)> _f) {
        f = _f;
        root_values = array;
        set_operate = true;
    }
    lint get_set_value(int a) {
        return root_values[leader(a)];
    }

    //regist count
    void regist_count(int a, int label) {
        if (!used_count) {
            used_count = true;
            count_in_set.assign(_n, std::map<int, int>());
        }
        count_in_set[leader(a)][label]++;
    }

    int get_count(int a, int label) {
        if (!used_count) return -1;
        return count_in_set[leader(a)][label];
    }

private:
    int _n;
    std::vector<int> parent_or_size;
    std::vector<std::map<int, int>> count_in_set;
    bool used_count = false;
    std::vector<lint> root_values;
    function<lint(lint, lint)> f;
    bool set_operate = false;
};


struct PartiallyPersistentUnionFind {
public:
    PartiallyPersistentUnionFind() {}

    PartiallyPersistentUnionFind(int sz) : data(sz, -1), last(sz, 1e9), add(sz) {
        for (auto& vs : add) vs.emplace_back(-1, -1);
    }

    bool merge(int x, int y, int t) {
        x = find(x, t);
        y = find(y, t);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        add[x].emplace_back(t, data[x]);
        data[y] = x;
        last[y] = t;
        return true;
    }

    int find(int x, int t) {
        if (t < last[x]) return x;
        return find(data[x], t);
    }

    int size(int x, int t) {
        x = find(x, t);
        return -prev(lower_bound(begin(add[x]), end(add[x]), make_pair(t, 0)))->second;
    }
private:
    std::vector<int> data;
    std::vector<int> last;
    std::vector<std::vector<std::pair<int, int>>> add;
};

lint N, M, Q, A, B;
int main() {
    cin >> N >> M;
    PartiallyPersistentUnionFind tree(N);
    REP(i, M) {
        cin >> A >> B; A--; B--;
        tree.merge(A, B, i);
    }
    cin >> Q;
    REP(i, Q) {
        cin >> A >> B; A--; B--;
        lint ng = -1, ok = M;
        while (ok - ng > 1) {
            lint mid = (ok + ng) / 2;
            if (tree.find(A, mid) == tree.find(B, mid)) ok = mid;
            else ng = mid;
        }
        if (ok == M) ok = -2;
        cout << ok + 1 << endk;
    }
}

Submission Info

Submission Time
Task H - Union Sets
User kaikey
Language C++ (GCC 9.2.1)
Score 600
Code Size 7189 Byte
Status AC
Exec Time 100 ms
Memory 10972 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 4 ms 3596 KB
sample_02.txt AC 3 ms 3488 KB
sample_03.txt AC 2 ms 3468 KB
subtask_1_1.txt AC 2 ms 3452 KB
subtask_1_10.txt AC 12 ms 3532 KB
subtask_1_11.txt AC 45 ms 3736 KB
subtask_1_12.txt AC 14 ms 6260 KB
subtask_1_13.txt AC 3 ms 3596 KB
subtask_1_14.txt AC 2 ms 3464 KB
subtask_1_15.txt AC 18 ms 3516 KB
subtask_1_16.txt AC 7 ms 3464 KB
subtask_1_17.txt AC 6 ms 3604 KB
subtask_1_18.txt AC 2 ms 3580 KB
subtask_1_19.txt AC 11 ms 5684 KB
subtask_1_2.txt AC 2 ms 3452 KB
subtask_1_20.txt AC 2 ms 3504 KB
subtask_1_21.txt AC 7 ms 3472 KB
subtask_1_22.txt AC 8 ms 4624 KB
subtask_1_23.txt AC 42 ms 9380 KB
subtask_1_24.txt AC 40 ms 9432 KB
subtask_1_25.txt AC 41 ms 9424 KB
subtask_1_26.txt AC 45 ms 9428 KB
subtask_1_27.txt AC 89 ms 10748 KB
subtask_1_28.txt AC 88 ms 10696 KB
subtask_1_29.txt AC 40 ms 9388 KB
subtask_1_3.txt AC 6 ms 3592 KB
subtask_1_30.txt AC 40 ms 9380 KB
subtask_1_31.txt AC 41 ms 9376 KB
subtask_1_32.txt AC 45 ms 9396 KB
subtask_1_33.txt AC 90 ms 10972 KB
subtask_1_34.txt AC 89 ms 10912 KB
subtask_1_35.txt AC 42 ms 9384 KB
subtask_1_36.txt AC 40 ms 9508 KB
subtask_1_37.txt AC 43 ms 9480 KB
subtask_1_38.txt AC 43 ms 9796 KB
subtask_1_39.txt AC 61 ms 10400 KB
subtask_1_4.txt AC 13 ms 7532 KB
subtask_1_40.txt AC 65 ms 10468 KB
subtask_1_41.txt AC 27 ms 3524 KB
subtask_1_42.txt AC 34 ms 3468 KB
subtask_1_43.txt AC 85 ms 8188 KB
subtask_1_44.txt AC 100 ms 10832 KB
subtask_1_45.txt AC 29 ms 3460 KB
subtask_1_46.txt AC 38 ms 9392 KB
subtask_1_5.txt AC 17 ms 3468 KB
subtask_1_6.txt AC 11 ms 6264 KB
subtask_1_7.txt AC 3 ms 3812 KB
subtask_1_8.txt AC 5 ms 3952 KB
subtask_1_9.txt AC 16 ms 3896 KB