Submission #401794

#	Time	Username	Problem	Language	Result	Execution time	Memory
401794		timmyfeng	Collapse (JOI18_collapse)	C++17	100 / 100	2760 ms	24280 KiB

collapse

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

const int N = 100000, B = 128;

vector<array<int, 3>> queries[N];
vector<int> adj[N];
bool visited[N];
int dsu[N];

int find(int u) {
    if (dsu[u] < 0) {
        return u;
    } else {
        dsu[u] = find(dsu[u]);
        return dsu[u];
    }
}

bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) {
        return false;
    }

    if (-dsu[u] > -dsu[v]) {
        swap(u, v);
    }

    dsu[v] += dsu[u];
    dsu[u] = v;
    return true;
}

void dfs(int u) {
    visited[u] = true;
    for (auto c : adj[u]) {
        if (!visited[c]) {
            dfs(c);
        }
    }
}

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
    int m = t.size(), q = w.size();
    vector<int> ans(q, n);

    for (int k = 0; k < 2; ++k) {
        map<array<int, 2>, int> in;
        vector<array<int, 4>> edges;
        for (int i = 0; i < m; ++i) {
            if (x[i] < y[i]) {
                swap(x[i], y[i]);
            }

            if (t[i] == 0) {
                in[{x[i], y[i]}] = i;
            } else {
                edges.push_back({x[i], y[i], in[{x[i], y[i]}], i});
                in.erase({x[i], y[i]});
            }
        }

        for (auto [e, i] : in) {
            edges.push_back({e[0], e[1], i, m});
        }

        sort(edges.begin(), edges.end());

        for (int i = 0; i < q; ++i) {
            queries[w[i] - w[i] % B].push_back({p[i], w[i], i});
        }

        for (int i = 0; i < m; i += B) {
            sort(queries[i].begin(), queries[i].end());

            vector<array<int, 4>> partial;
            fill(dsu, dsu + n, -1);
            int count = 0;

            int j = 0;
            for (auto [l, s, id] : queries[i]) {
                while (j < (int) edges.size() && edges[j][0] <= l) {
                    auto [u, v, a, b] = edges[j++];
                    if (a <= i && min(m, i + B) <= b) {
                        count += unite(u, v);
                    } else if (!(b <= i || min(m, i + B) <= a)) {
                        partial.push_back({u, v, a, b});
                    }
                }

                vector<int> nodes;
                for (auto [u, v, a, b] : partial) {
                    if (a <= s && s < b) {
                        u = find(u), v = find(v);
                        adj[u].push_back(v);
                        adj[v].push_back(u);
                        nodes.push_back(u);
                        nodes.push_back(v);
                    }
                }

                int res = 0;
                for (auto u : nodes) {
                    if (!visited[u]) {
                        --res;
                        ++ans[id];
                        dfs(u);
                    }
                }

                for (auto u : nodes) {
                    if (visited[u]) {
                        visited[u] = false;
                        adj[u].clear();
                        ++res;
                        --ans[id];
                    }
                }

                ans[id] -= count;
            }

            queries[i].clear();     
        }

        for (int i = 0; i < m; ++i) {
            x[i] = n - 1 - x[i];
            y[i] = n - 1 - y[i];
        }

        for (int i = 0; i < q; ++i) {
            p[i] = n - 2 - p[i];
        }
    }

    return ans;
}

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