Submission #1215942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215942		badge881	Collapse (JOI18_collapse)	C++20	100 / 100	3116 ms	9340 KiB

collapse

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

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
    const int S = 320;

    int C = X.size(), Q = W.size();

    int cnt = 0;
    vector<int> lab(N, -1);
    vector<array<int, 2>> his;
    auto init = [&]()
    {
        fill(lab.begin(), lab.end(), -1);
        cnt = 0;
    };
    auto find = [&](int u) -> int
    {
        while (lab[u] >= 0)
            u = lab[u];
        return u;
    };
    auto unite = [&](int u, int v, bool keep)
    {
        u = find(u), v = find(v);
        if (u == v)
        {
            if (keep)
                his.push_back({-1, -1});
            return;
        }
        if (lab[u] > lab[v])
            swap(u, v);
        if (keep)
            his.push_back({v, lab[v]});
        cnt++;
        lab[u] += lab[v];
        lab[v] = u;
    };
    auto restore = [&]()
    {
        while (his.size())
        {
            auto e = his.back();
            his.pop_back();
            if (~e[0])
            {
                --cnt;
                int &p = lab[e[0]];
                lab[p] -= e[1];
                p = e[1];
            }
        }
    };
    vector<array<int, 2>> comp;
    for (int i = 0; i < C; i++)
    {
        if (X[i] > Y[i])
            swap(X[i], Y[i]);
        comp.push_back({X[i], Y[i]});
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = comp.size();
    vector<int> pos(C);
    for (int i = 0; i < C; i++)
    {
        T[i] ^= 1;
        pos[i] = lower_bound(comp.begin(), comp.end(), array<int, 2>{X[i], Y[i]}) - comp.begin();
    }
    vector<array<int, 3>> queries;
    vector<int> res(Q);
    for (int i = 0; i < Q; i++)
    {
        queries.push_back({P[i], W[i], i});
        res[i] = N;
    }
    sort(queries.begin(), queries.end(), [&](const auto &u, const auto &v)
         { return u[1] < v[1]; });
    vector<bool> tog(M), cur(M), nw(M);
    int ptr = 0;
    for (int i = 0; i < C; i += S)
    {
        int l = i, r = min(C - 1, i + S - 1);
        for (int j = l; j <= r; j++)
            tog[pos[j]] = 1;

        vector<int> add;
        vector<array<int, 2>> cands;
        for (int j = 0; j < M; j++)
            if (!tog[j] && cur[j])
                cands.push_back(comp[j]);
            else if (tog[j])
                add.push_back(j);
        vector<array<int, 3>> ord;
        while (ptr < Q && queries[ptr][1] <= r)
            ord.push_back(queries[ptr++]);

        sort(ord.begin(), ord.end());
        sort(cands.begin(), cands.end(), [&](const auto &u, const auto &v)
             { return u[1] < v[1]; });
        init();
        int k = 0;
        for (auto [x, d, id] : ord)
        {
            while (k < cands.size() && cands[k][1] <= x)
            {
                unite(cands[k][0], cands[k][1], 0);
                k++;
            }
            for (int j = l; j <= d; j++)
                nw[pos[j]] = T[j];
            for (int id : add)
            {
                if (nw[id] && comp[id][1] <= x)
                    unite(comp[id][0], comp[id][1], 1);
                nw[id] = cur[id];
            }
            res[id] -= cnt;
            restore();
        }
        init();
        reverse(ord.begin(), ord.end());
        sort(cands.rbegin(), cands.rend());
        k = 0;
        for (auto [x, d, id] : ord)
        {
            while (k < cands.size() && cands[k][0] > x)
            {
                unite(cands[k][0], cands[k][1], 0);
                k++;
            }
            for (int j = l; j <= d; j++)
                nw[pos[j]] = T[j];
            for (int id : add)
            {
                if (nw[id] && comp[id][0] > x)
                    unite(comp[id][0], comp[id][1], 1);
                nw[id] = cur[id];
            }
            res[id] -= cnt;
            restore();
        }
        for (int j = l; j <= r; j++)
        {
            tog[pos[j]] = 0;
            cur[pos[j]] = T[j];
            nw[pos[j]] = cur[pos[j]];
        }
    }
    return res;
}

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