Submission #706696

#	Time	Username	Problem	Language	Result	Execution time	Memory
706696		bebra	Collapse (JOI18_collapse)	C++17	0 / 100	15041 ms	64628 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


struct DSU {
    vector<int> parent;
    vector<int> size;
    vector<pair<int, int>> changes;
    int cnt;

    DSU() {}

    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        size.assign(n, 1);
        cnt = 0;
    }

    int find(int v) {
        if (parent[v] == v) {
            return v;
        } else {
            return find(parent[v]);
        }
    }

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (size[u] > size[v]) swap(u, v);
        changes.emplace_back(u, v);
        parent[u] = v;
        size[v] += size[u];
        ++cnt;
    }

    void save() {
        changes.emplace_back(-1, -1);
    }

    void rollback() {
        while (changes.back().first != -1) {
            auto [u, v] = changes.back();
            changes.pop_back();

            parent[u] = u;
            size[v] -= size[u];
            --cnt;
        }
        changes.pop_back();
    }
};


const int MAX_N = 1 << 18;

vector<pair<int, int>> tree[2 * MAX_N - 1];
vector<pair<int, int>> queries[2 * MAX_N - 1];
int cnt[2 * MAX_N - 1];
int ans[MAX_N];

void update(int l, int r, int v, int lq, int rq, const pair<int, int>& edge) {
    if (lq <= l && r <= rq) {
        tree[v].push_back(edge);
        return;
    } else if (l >= rq || r <= lq) {
        return;
    }
    int m = (l + r) / 2;
    update(l, m, 2 * v + 1, lq, rq, edge);
    update(m, r, 2 * v + 2, lq, rq, edge);
}

void update(int lq, int rq, const pair<int, int>& edge) {
    update(0, MAX_N, 0, lq, rq, edge);
}

void add_query(int pos, int x, int idx) {
    int v = pos + MAX_N - 1;
    queries[pos].emplace_back(x, idx);
    ++cnt[v];
    while (v > 0) {
        v = (v - 1) / 2;
        ++cnt[v];
    }
}

const int INF = 1e9 + 5;

const int BLOCK_SIZE = 10;
const int BLOCKS_N = MAX_N / BLOCK_SIZE + 5;
set<pair<int, int>> max_block_edges[BLOCKS_N];
set<pair<int, int>> min_block_edges[BLOCKS_N];
DSU empty_dsu;
DSU max_block_dsu[BLOCKS_N];
DSU min_block_dsu[BLOCKS_N];

vector<pair<int, int>> max_edges, min_edges;
map<pair<int, int>, int> max_edge_idx, min_edge_idx;
int n;


void add_edge(int u, int v) {
    {
        int max_idx = max_edge_idx.at({u, v});
        int curr_block = max_idx / BLOCK_SIZE;
        max_block_edges[curr_block].emplace(u, v);
        for (int i = curr_block + 1; i < BLOCKS_N; ++i) {
            max_block_dsu[i].unite(u, v);    
        }
    }
    {
        int min_idx = min_edge_idx.at({u, v});
        int curr_block = min_idx / BLOCK_SIZE;
        min_block_edges[curr_block].emplace(u, v);
        for (int i = curr_block - 1; i >= 0; --i) {
            min_block_dsu[i].unite(u, v);    
        }
    }
}

void save_state() {
    for (int i = 0; i < BLOCKS_N; ++i) {
        max_block_dsu[i].save();
        min_block_dsu[i].save();
    }
}

void rollback_state() {
    for (int i = 0; i < BLOCKS_N; ++i) {
        max_block_dsu[i].rollback();
        min_block_dsu[i].rollback();
    }
}

int get_comps(int x) {
    int res = n;
    {
        auto it = upper_bound(max_edges.begin(), max_edges.end(), make_pair(x, -1), [&](const auto& lhs, const auto& rhs) {
            return max(lhs.first, lhs.second) < max(rhs.first, rhs.second);
        });
        if (it != max_edges.begin()) {
            --it;

            int block = (it - max_edges.begin()) / BLOCK_SIZE;
            auto& curr_dsu = empty_dsu;
            if (block > 0) {
                curr_dsu = max_block_dsu[block - 1];
            }
            curr_dsu.save();
            for (const auto& [u, v] : max_block_edges[block]) {
                if (max(u, v) <= x) {
                    curr_dsu.unite(u, v);
                }
            }
            res -= curr_dsu.cnt;
            curr_dsu.rollback();
        }
    }
    {
        auto it = upper_bound(min_edges.begin(), min_edges.end(), make_pair(x, INF), [&](const auto& lhs, const auto& rhs) {
            return min(lhs.first, lhs.second) < min(rhs.first, rhs.second);
        });

        if (it != min_edges.end()) {
            int block = (it - min_edges.begin()) / BLOCK_SIZE;
            auto& curr_dsu = empty_dsu;
            if (block + 1 < BLOCKS_N) {
                curr_dsu = min_block_dsu[block + 1];
            }
            curr_dsu.save();
            for (const auto& [u, v] : min_block_edges[block]) {
                if (min(u, v) > x) {
                    curr_dsu.unite(u, v);
                }
            }
            res -= curr_dsu.cnt;
            curr_dsu.rollback();
        }
    }
    return res;
}

void remove_edge(int u, int v) {
    {
        int max_idx = max_edge_idx.at({u, v});
        int curr_block = max_idx / BLOCK_SIZE;
        max_block_edges[curr_block].erase({u, v});
    }
    {
        int min_idx = min_edge_idx.at({u, v});
        int curr_block = min_idx / BLOCK_SIZE;
        min_block_edges[curr_block].erase({u, v});
    }
}


void dfs(int l, int r, int v) {
    save_state();

    for (const auto& [e1, e2] : tree[v]) {
        add_edge(e1, e2);
    }

    if (l == r - 1) {
        for (const auto& [x, idx] : queries[l]) {
            ans[idx] = get_comps(x);
        }
    } else {
        int m = (l + r) / 2;
        if (cnt[2 * v + 1] > 0) {
            dfs(l, m, 2 * v + 1);
        }
        if (cnt[2 * v + 2] > 0) {
            dfs(m, r, 2 * v + 2);
        }
    }

    for (const auto& [e1, e2] : tree[v]) {
        remove_edge(e1, e2);
    }

    rollback_state();
}


vector<int> simulateCollapse(int _n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
    n = _n;
    int c = T.size();
    int q = W.size();

    map<pair<int, int>, int> opened_edges;
    for (int i = 0; i < c; ++i) {
        int t = T[i];
        int u = X[i];
        int v = Y[i];
        if (u > v) swap(u, v);

        max_edges.emplace_back(u, v);

        if (t == 0) {
            opened_edges[{u, v}] = i;
        } else {
            int l = opened_edges[{u, v}];
            opened_edges.erase({u, v});
            update(l, i, make_pair(u, v));
        }
    }

    for (const auto& [edge, l] : opened_edges) {
        update(l, c, edge);
    }

    for (int i = 0; i < q; ++i) {
        int pos = W[i];
        int x = P[i];
        add_query(pos, x, i);
    }

    sort(max_edges.begin(), max_edges.end());
    max_edges.resize(unique(max_edges.begin(), max_edges.end()) - max_edges.begin());
    min_edges = max_edges;

    sort(max_edges.begin(), max_edges.end(), [&](const auto& lhs, const auto& rhs) {
        return max(lhs.first, lhs.second) < max(rhs.first, rhs.second);
    });
    for (int i = 0; i < (int)max_edges.size(); ++i) {
        max_edge_idx[max_edges[i]] = i;
    }

    sort(max_edges.begin(), max_edges.end(), [&](const auto& lhs, const auto& rhs) {
        return min(lhs.first, lhs.second) < min(rhs.first, rhs.second);
    });
    for (int i = 0; i < (int)min_edges.size(); ++i) {
        min_edge_idx[min_edges[i]] = i;
    }

    empty_dsu = DSU(n);
    for (int i = 0; i < BLOCKS_N; ++i) {
        max_block_dsu[i] = DSU(n);
        min_block_dsu[i] = DSU(n);
    }

    dfs(0, MAX_N, 0);

    vector<int> res(q);
    for (int i = 0; i < q; ++i) {
        res[i] = ans[i];
    }
    return res;
}

// int main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int _n, c, q;
//     cin >> _n >> c >> q;

//     vector<int> T(c), X(c), Y(c);
//     for (int i = 0; i < c; ++i) {
//         cin >> T[i] >> X[i] >> Y[i];
//     }

//     vector<int> W(q), P(q);
//     for (int i = 0; i < q; ++i) {
//         cin >> W[i] >> P[i];
//     }

//     for (auto x : simulateCollapse(_n, T, X, Y, W, P)) {
//         cout << x << '\n';
//     }

//     return 0;
// }



/*
5 7 2
0 1 3
1 3 1
0 1 2
0 0 2
0 1 0
1 0 1
0 4 1
4 2
5 1

right:
3
5

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35