Submission #1261823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261823		icebear	Collapse (JOI18_collapse)	C++20	30 / 100	1463 ms	36032 KiB

collapse

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

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
const int S = 500;
int n, q, c;
struct DSU {
    vector<int> lab;
    vector<array<int, 4>> history;
    int connected;
    DSU(int n = 0): lab(n, -1), connected(0) {}

    int root(int v) {
        return (lab[v] < 0 ? v : root(lab[v]));
    }

    bool unite(int u, int v) {
        u = root(u); v = root(v);
        if (u == v) return false;
        if (lab[u] > lab[v]) swap(u, v);
        history.pb({u, v, lab[u], lab[v]});
        connected++;
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    void roll_back() {
        while(!history.empty()) {
            auto tmp = history.back(); history.pop_back();
            lab[tmp[0]] = tmp[2];
            lab[tmp[1]] = tmp[3];
            connected--;
        }
    }
} dsu;

vector<ii> event[N];
vector<int> up[N], down[N], upB[N], downB[N];
vector<int> queries[N];

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
    n = N;
    c = T.size();
    q = W.size();

    REP(i, c) if (X[i] > Y[i])
        swap(X[i], Y[i]);

    vector<int> query;
    REP(i, q) query.pb(i);
    sort(all(query), [&](int &x, int &y){
        return W[x] < W[y];
    });

    vector<int> res(q, 0);
    vector<bool> is_del(c, false);
    vector<int> index(c, c);
    map<ii, int> id;
    REP(i, c) {
        if (T[i] == 0) {
            id[{X[i], Y[i]}] = i;
        } else index[i] = id[{X[i], Y[i]}];
    }

    int Q = 0;
    for(int B = 0; B < c; B += S) {
        int L = B, R = min(c, B + S) - 1;

        int _Q = Q;
        for(; _Q < q && W[query[_Q]] <= R; _Q++) {
            int i_q = query[_Q];
            queries[P[i_q]].pb(i_q);
        }

        vector<bool> up_check(n, false), down_check(n, false);
        vector<int> ups, downs;
        vector<int> edges_out;
        FOR(i, L, R) {
            if (T[i] == 0) {
                if (up_check[Y[i]] == false) {
                    ups.pb(Y[i]);
                    up_check[Y[i]] = true;
                }

                if (down_check[X[i]] == false) {
                    downs.pb(X[i]);
                    down_check[X[i]] = true;
                }

                upB[Y[i]].pb(i);
                downB[X[i]].pb(i);
            } else {
                if (index[i] < L) edges_out.pb(i), is_del[index[i]] = true;
            }
        }
        sort(all(ups));
        sort(all(downs), greater<int>());

        // answer query up
        dsu = DSU(n);
        REP(w, n) {
            for(int &i : up[w]) if (!is_del[i])
                dsu.unite(X[i], Y[i]);
            dsu.history.clear();
            for(int &i_q : queries[w]) {
                FOR(i, L, W[i_q]) if (T[i] == 1) {
                    is_del[index[i]] = true;
                }
                for(int &i_del : edges_out) {
                    // connect edges out of block yet deleted
                    if (i_del <= W[i_q]) break;
                    int id_edge = index[i_del];
                    if (Y[id_edge] <= w) dsu.unite(X[id_edge], Y[id_edge]);
                }
                for(int &i : ups) {
                    if (i > w) break;
                    for(int &j : upB[i]) if (j <= W[i_q] && !is_del[j])
                        dsu.unite(X[j], Y[j]);
                }
                res[i_q] += w + 1 - dsu.connected; // scc with index <= p
                dsu.roll_back();
                // ignore edges out of block
                FOR(i, L, W[i_q]) if (T[i] == 1 && L <= index[i]) {
                    is_del[index[i]] = false;
                }
            }
        }

        // answer query down
        dsu = DSU(n);
        RED(w, n) {
            for(int &i_q : queries[w]) {
                FOR(i, L, W[i_q]) if (T[i] == 1) {
                    is_del[index[i]] = true;
                }
                for(int &i_del : edges_out) {
                    // connect edges out of block yet deleted
                    if (i_del <= W[i_q]) continue;
                    int id_edge = index[i_del];
                    if (X[id_edge] > P[i_q]) dsu.unite(X[id_edge], Y[id_edge]);
                }
                for(int &i : downs) {
                    if (i <= w) break;
                    for(int &j : downB[i]) if (j <= W[i_q] && !is_del[j])
                        dsu.unite(X[j], Y[j]);
                }
                res[i_q] += n - (w + 1) - dsu.connected;
                dsu.roll_back();
                // ignore edges out of block
                FOR(i, L, W[i_q]) if (T[i] == 1 && L <= index[i]) {
                    is_del[index[i]] = false;
                }
            }

            for(int &i : down[w]) if (!is_del[i])
                dsu.unite(X[i], Y[i]);
            dsu.history.clear();
        }

        // clear query + add edge in current block
        for(; Q < _Q; Q++) {
            int i_q = query[Q];
            queries[P[i_q]].clear();
        }

        FOR(i, L, R) if (T[i] == 1)
            is_del[index[i]] = true;
        FOR(i, L, R) {
            if (!is_del[i] && T[i] == 0) {
                up[Y[i]].pb(i);
                down[X[i]].pb(i);
            }
            upB[Y[i]].clear();
            downB[X[i]].clear();
        }
    }

    return res;
}

// int main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     auto ans = simulateCollapse(5, {0, 1, 0, 0, 0, 1, 0}, {1, 3, 1, 0, 1, 0, 4}, {3, 1, 2, 2, 0, 1, 1},
//                                 {6, 6, 6, 6, 6}, {0, 1, 2, 3, 4});
//     for(int x : ans) cout << x << ' '; cout << '\n';
//     return 0;
// }

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