Submission #979819

#	Time	Username	Problem	Language	Result	Execution time	Memory
979819		peterandvoi	Collapse (JOI18_collapse)	C++17	100 / 100	1359 ms	83572 KiB

collapse

#include <bits/stdc++.h>

#include "collapse.h"

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int S = 320;

vector<int> simulateCollapse(int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
    int Q = int(W.size()), C = int(X.size());
    vector<int> ord(Q), res(Q);
    vector<pair<int, int>> edges;
    for (int i = 0; i < C; ++i) {
        if (X[i] > Y[i]) {
            swap(X[i], Y[i]);
        }
        edges.emplace_back(X[i], Y[i]);
    }
    sort(edges.begin(), edges.end());
    edges.erase(unique(edges.begin(), edges.end()), edges.end());
    int m = int(edges.size());
    vector<int> idx(C);
    for (int i = 0; i < C; ++i) {
        idx[i] = lower_bound(edges.begin(), edges.end(), make_pair(X[i], Y[i])) - edges.begin();
    }
    vector<vector<int>> qry(C);
    for (int i = 0; i < Q; ++i) {
        qry[W[i]].emplace_back(i);
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return W[i] < W[j];
    });
    vector<int> lab(n, -1);
    vector<pair<int, int>> his;
    int cc = n;
    auto get = [&](auto get, int u) -> int {
        return lab[u] < 0 ? u : get(get, lab[u]);
    };
    auto unite = [&](int u, int v, bool rb) {
        u = get(get, u), v = get(get, v);
        if (u ^ v) {
            if (lab[u] > lab[v]) {
                swap(u, v);
            }
            if (rb) {
                his.emplace_back(v, lab[v]);
            }
            lab[u] += lab[v];
            lab[v] = u;
            cc--;
        }
    };
    auto rollback = [&]() {
        while (his.size()) {
            auto [v, sz] = his.back();
            his.pop_back();
            int u = lab[v];
            lab[u] -= sz;
            lab[v] = sz;
            cc++;
        }
    };
    auto reset = [&]() {
        cc = n;
        fill(lab.begin(), lab.end(), -1);
        his.clear();
    };
    vector<int> inc(m);
    iota(inc.begin(), inc.end(), 0);
    auto dec = inc;
    sort(inc.begin(), inc.end(), [&](int i, int j) {
        return edges[i].second < edges[j].second;
    });
    sort(dec.begin(), dec.end(), [&](int i, int j) {
        return edges[i].first > edges[j].first;
    });
    vector<bool> cant(m, false), state(m, false);
    vector<vector<int>> gL(Q), gR(Q);
    int time = 0;
    for (int s = 0; s < C; s += S) {
        int l = s, r = min(C, s + S) - 1;
        vector<int> cands;
        for (int i = l; i <= r; ++i) {
            cands.emplace_back(idx[i]);
        }
        sort(cands.begin(), cands.end());
        cands.erase(unique(cands.begin(), cands.end()), cands.end());
        for (int id : cands) {
            cant[id] = true;
        }
        vector<int> v;
        for (int i = l; i <= r; ++i) {
            state[idx[i]] = 1 - state[idx[i]];
            for (int id : qry[i]) {
                v.emplace_back(id);
                for (int u : cands) {
                    if (state[u]) {
                        if (edges[u].second <= P[id]) {
                            gL[id].emplace_back(u);
                        } else if (edges[u].first > P[id]) {
                            gR[id].emplace_back(u);
                        }
                    }
                }
            }
        }
        sort(v.begin(), v.end(), [&](int i, int j) {
            return P[i] < P[j];
        });
        reset();
        int j = 0;
        for (int id : v) {
            while (j < m && edges[inc[j]].second <= P[id]) {
                int i = inc[j];
                if (!cant[i] && state[i]) {
                    unite(edges[i].first, edges[i].second, false);
                }
                j++;
            }
            for (int k : gL[id]) {
                unite(edges[k].first, edges[k].second, true);
            }
            res[id] += cc - n + P[id] + 1;
            rollback();
        }
        reverse(v.begin(), v.end());
        reset();
        j = 0;
        for (int id : v) {
            while (j < m && edges[dec[j]].first > P[id]) {
                int i = dec[j];
                if (!cant[i] && state[i]) {
                    unite(edges[i].first, edges[i].second, false);
                }
                j++;
            }
            for (int k : gR[id]) {
                unite(edges[k].first, edges[k].second, true);
            }
            res[id] += cc - P[id] - 1;
            rollback();
        }
        for (int id : cands) {
            cant[id] = false;
        }
    }
    return res;
}

#ifdef ngu
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    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];
    }
    auto res = simulateCollapse(n, T, X, Y, W, P);
    for (int i = 0; i < Q; ++i) {
        cout << res[i] << " ";
    }
}
#endif ngu

Compilation message (stderr)

collapse.cpp:180:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  180 | #endif ngu
      |        ^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:86:9: warning: unused variable 'time' [-Wunused-variable]
   86 |     int time = 0;
      |         ^~~~

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