Submission #338464

#	Time	Username	Problem	Language	Result	Execution time	Memory
338464		KoD	Collapse (JOI18_collapse)	C++17	35 / 100	364 ms	23628 KiB

collapse

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct DSU {
    Vec<int> par;
    int cmp;
    std::stack<std::tuple<int, int, int, int, int>> stack;

    DSU(const int n): par(n, -1), cmp(n) { }

    int find(int x) const {
        while (par[x] >= 0) {
            x = par[x];
        }
        return x;
    }

    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return 0;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        stack.emplace(x, par[x], y, par[y], cmp);
        par[x] += par[y];
        par[y] = x;
        cmp -= 1;
        return 1;
    }

    void rollback() {
        const auto [i, x, j, y, c] = stack.top();
        stack.pop();
        par[i] = x;
        par[j] = y;
        cmp = c;
    }
};

struct Solver {
    Vec<Vec<std::pair<int, int>>> edges;

    Solver(const int t) {
        int n = 1;
        while (n < t) {
            n <<= 1;
        }
        edges.resize(2 * n);
    }

    void add(int u, int v, int l, int r) {
        l += size();
        r += size();
        while (l < r) {
            if (l & 1) {
                edges[l].emplace_back(u, v);
                l += 1;
            }
            l >>= 1;
            if (r & 1) {
                r -= 1;
                edges[r].emplace_back(u, v);
            }
            r >>= 1;
        }
    }

    void dfs(int k, DSU &uf, Vec<int> &vec) {
        int steps = 0;
        for (const auto [u, v]: edges[k]) {
            steps += uf.merge(u, v);
        }
        if (k >= size()) {
            vec[k - size()] = uf.cmp;
        }
        else {
            dfs(k * 2, uf, vec);
            dfs(k * 2 + 1, uf, vec);
        }
        while (steps--) {
            uf.rollback();
        }
    }

    Vec<int> solve(int n, int t) {
        DSU uf(n);
        Vec<int> ret(size());
        dfs(1, uf, ret);
        ret.resize(t);
        ret.shrink_to_fit();
        return ret;
    }

    int size() const {
        return edges.size() / 2;
    }
};

struct FastDSU {
    Vec<int> par;
    int cmp;

    FastDSU(const int n): par(n, -1), cmp(n) { }

    int find(int x) {
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        cmp -= 1;
    }
};

Vec<int> simulateCollapse(int N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
    const int C = T.size();
    const int Q = W.size();
    Vec<int> ret(Q);
    if (std::count(P.begin(), P.end(), P.front()) == Q) {
        Solver sol(C);
        std::map<std::pair<int, int>, int> state;
        const int bad = P.front();
        for (int i = 0; i < C; ++i) {
            const auto p = std::minmax(X[i], Y[i]);
            if (p.second <= bad || p.first > bad) {
                if (state.find(p) == state.end() || state[p] == -1) {
                    state[p] = i;
                }
                else {
                    sol.add(p.first, p.second, state[p], i);
                    state[p] = -1;
                }
            }
        }
        for (const auto &[p, v]: state) {
            if (v != -1) {
                sol.add(p.first, p.second, v, C);
            }
        } 
        const auto vec = sol.solve(N, C);
        for (int i = 0; i < Q; ++i) {
            ret[i] = vec[W[i]];
        }
    }
    else if (N <= 5000 && C <= 5000 && Q <= 5000) {
        Vec<std::pair<int, int>> edges;
        edges.reserve(C);
        for (int i = 0; i < C; ++i) {
            edges.push_back(std::minmax(X[i], Y[i]));
        }
        std::sort(edges.begin(), edges.end());
        edges.erase(std::unique(edges.begin(), edges.end()), edges.end());
        const int E = edges.size();
        Vec<int> index(C);
        for (int i = 0; i < C; ++i) {
            const std::pair<int, int> p = std::minmax(X[i], Y[i]);
            index[i] = std::lower_bound(edges.begin(), edges.end(), p) - edges.begin();
        }
        for (int i = 0; i < Q; ++i) {
            Vec<bool> use(E);
            for (int j = 0; j <= W[i]; ++j) {
                if (std::max(X[j], Y[j]) <= P[i] || std::min(X[j], Y[j]) > P[i]) {
                    use[index[j]] = !use[index[j]];
                }
            }
            FastDSU dsu(N);
            for (int j = 0; j < E; ++j) {
                if (use[j]) {
                    dsu.merge(edges[j].first, edges[j].second);
                }
            }
            ret[i] = dsu.cmp;
        }
    }
    return ret;
}

#ifdef __APPLE__
int main() {
    int N, C, Q;
    std::cin >> N >> C >> Q;
    Vec<int> T(C), X(C), Y(C);

}
#endif

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