oj.uz

Submission #338458

# Submission time Handle Problem Language Result Execution time Memory
338458 2020-12-23T07:45:59 Z KoD Collapse (JOI18_collapse) C++17
0 / 100
 28 ms 2624 KB 
#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;
    }
};

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()) == N) {
        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[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]];
        }
    }
    return ret;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -