제출 #425001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425001		CodePlatina	Collapse (JOI18_collapse)	C++17	100 / 100	7866 ms	420980 KiB

collapse

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
const int INF = (int)1e9 + 7;
const int Q = 320;

using namespace std;

vector<pii> eg;
vector<pii> lf;
map<pii, int> M;
vector<int> lsu[101010];
vector<int> lsd[101010];
vector<pii> qr[101010];

struct UF
{
    int par[101010];
    short rnk[101010];
    int pnt;
    int cnt, __cnt;
    vector<pii> rec;

    UF(void) : pnt(0), cnt(0), __cnt(0), rec() { for(int i = 0; i < 101010; ++i) par[i] = i, rnk[i] = 0; }
    int fnd(int x) { return x == par[x] ? x : fnd(par[x]); }
    void uni(int x, int y)
    {
        x = fnd(x), y = fnd(y);
        if(x == y) return;
        if(rnk[x] == rnk[y])
        {
            rec.push_back({0, x});
            rec.push_back({1, y});
            ++rnk[x];
            par[y] = x;
        }
        else if(rnk[x] > rnk[y])
        {
            rec.push_back({1, y});
            par[y] = x;
        }
        else
        {
            rec.push_back({1, x});
            par[x] = y;
        }
        ++cnt;
    }
    void save(void) { pnt = (int)rec.size(); __cnt = cnt; }
    void rollback(void)
    {
        while((int)rec.size() > pnt)
        {
            auto [c, x] = rec.back();
            if(c == 0) --rnk[x];
            else par[x] = x;
            rec.pop_back();
        }
        cnt = __cnt;
    }
}uf[320];

vector<int> ind[320];

vector<int> simulateCollapse(int N, vector<int> C, vector<int> X, vector<int> Y, vector<int> W, vector<int>P)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = N, m = C.size(), T = W.size();
    for(int i = 0; i < m; ++i)
    {
        int c = C[i], x = X[i], y = Y[i];
        if(x > y) swap(x, y);

        if(c == 0)
        {
            M[{x, y}] = (int)eg.size();
            eg.push_back({x, y});
            lf.push_back({i, m});
        }
        else
        {
            lf[M[{x, y}]].ss = i;
            M.erase({x, y});
        }
    }
    for(int i = 0; i < (int)eg.size(); ++i)
    {
        if(eg[i].ff > 0) lsd[eg[i].ff - 1].push_back(i);
        lsu[eg[i].ss].push_back(i);
    }

    for(int i = 0; i < T; ++i)
    {
        int x = W[i], y = P[i];
        qr[y].push_back({x, i});
    }

    vector<int> ans(T); for(auto &i : ans) i = n;
    for(int i = 0; i < n; ++i)
    {
        for(int k = 0; k < (int)lsu[i].size(); ++k)
        {
            auto [x, y] = eg[lsu[i][k]];
            auto [s, e] = lf[lsu[i][k]];
            for(int j = s / Q; j <= (e - 1) / Q; ++j)
            {
                int l = j * Q, r = l + Q;
                if(s <= l && r <= e) uf[j].uni(x, y);
                else ind[j].push_back(lsu[i][k]);
            }
        }

        for(auto [t, q] : qr[i])
        {
            int j = t / Q;
            uf[j].save();
            for(int k = 0; k < (int)ind[j].size(); ++k)
            {
                auto [x, y] = eg[ind[j][k]];
                auto [s, e] = lf[ind[j][k]];
                if(s <= t && t < e) uf[j].uni(x, y);
            }
            ans[q] -= uf[j].cnt;
            uf[j].rollback();
        }
    }

    for(int i = 0; i < 320; ++i)
    {
        uf[i].pnt = uf[i].cnt = uf[i].__cnt = 0;
        uf[i].rollback();
        ind[i].clear();
        ind[i].shrink_to_fit();
    }

    for(int i = n - 1; i >= 0; --i)
    {
        for(int k = 0; k < (int)lsd[i].size(); ++k)
        {
            auto [x, y] = eg[lsd[i][k]];
            auto [s, e] = lf[lsd[i][k]];
            for(int j = s / Q; j <= (e - 1) / Q; ++j)
            {
                int l = j * Q, r = l + Q;
                if(s <= l && r <= e) uf[j].uni(x, y);
                else ind[j].push_back(lsd[i][k]);
            }
        }

        for(auto [t, q] : qr[i])
        {
            int j = t / Q;
            uf[j].save();
            for(int k = 0; k < (int)ind[j].size(); ++k)
            {
                auto [x, y] = eg[ind[j][k]];
                auto [s, e] = lf[ind[j][k]];
                if(s <= t && t < e) uf[j].uni(x, y);
            }
            ans[q] -= uf[j].cnt;
            uf[j].rollback();
        }
    }

	return ans;
}

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