oj.uz

Submission #338460

# Submission time Handle Problem Language Result Execution time Memory
338460 2020-12-23T07:50:40 Z KoD Collapse (JOI18_collapse) C++17
30 / 100
 172 ms 23372 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()) == 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]];
        }
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2284 KB Output is correct
2 Correct 28 ms 2284 KB Output is correct
3 Correct 84 ms 14700 KB Output is correct
4 Correct 30 ms 2284 KB Output is correct
5 Correct 117 ms 15468 KB Output is correct
6 Correct 34 ms 3692 KB Output is correct
7 Correct 154 ms 23372 KB Output is correct
8 Correct 128 ms 17132 KB Output is correct
9 Correct 31 ms 2924 KB Output is correct
10 Correct 33 ms 2668 KB Output is correct
11 Correct 34 ms 2924 KB Output is correct
12 Correct 144 ms 18156 KB Output is correct
13 Correct 166 ms 20704 KB Output is correct
14 Correct 166 ms 23244 KB Output is correct
15 Correct 172 ms 22348 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2316 KB Output is correct
2 Incorrect 28 ms 2284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -