Submission #940118

#	Time	Username	Problem	Language	Result	Execution time	Memory
940118		sleepntsheep	Collapse (JOI18_collapse)	C++17	30 / 100	218 ms	45624 KiB

collapse

#include "collapse.h"
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <utility>

#define S 400
#define N 100000

struct dsu
{
    std::vector<int>p;
    std::stack<std::pair<int, int> > save;

    dsu() {}
    dsu(int n): p(n, -1), savemode(0), comp(n) {}
    int savemode, comp;

    int find(int x) { return p[x] < 0 ? x : find(p[x]); }

    bool unite(int x, int y)
    {
        if ((x = find(x)) == (y = find(y))) return false;
        if (-p[x] < -p[y]) std::swap(x, y);
        save.push(std::make_pair(y, p[y]));
        p[x] += p[y];
        p[y] = x;
        --comp;
        return true;
    }

    void rollback()
    {
        auto [y, py] = save.top();
        save.pop();
        int x = p[y];
        p[x] -= py;
        p[y] = py;
        ++comp;
    }
};

int n, c, q;
std::vector<std::pair<int, int> > t[N<<2];
std::vector<std::pair<int, int > > at[N];
std::vector<int> ans;

dsu ds[999];

void ins(int v, int l, int r, int x, int y, int ex, int ey)
{
    if (r < x || y < l) return;
    if (x <= l && r <= y)
    {
        t[v].emplace_back(ex, ey);
        return;
    }
    ins(2*v+1, l, (l+r)/2, x, y, ex, ey);
    ins(2*v+2, (l+r)/2+1, r, x, y, ex, ey);
}

int ban;

dsu ds1;

void dfs(int v, int l, int r)
{
    //printf("%d %d %d\n",v,l,r);fflush(stdout);
    int nrb = 0;
    for (auto[x,y]:t[v])
    {
        if (x <= ban && ban < y) continue;
        nrb += ds1.unite(x, y);
    }

    if (l-r) dfs(2*v+1,l,(l+r)/2),dfs(2*v+2,(l+r)/2+1,r);
    else
    {
        for (auto[i,_]:at[l])
        {
            ans[i] = ds1.comp;
        }
    }

    while (nrb--) ds1.rollback();
}

std::vector<int> simulateCollapse(
	int n0,
	std::vector<int> t,
	std::vector<int> x,
	std::vector<int> y,
	std::vector<int> w,
	std::vector<int> p
) {
    n=n0;c=t.size();q=w.size();

    ban = p[0];

    {
        std::map<std::pair<int, int>, int> st;
        for (int i = 0; i < t.size(); ++i)
        {
            if(x[i] > y[i]) std::swap(x[i], y[i]);

            if (t[i] == 0)
            {
                st[std::make_pair(x[i], y[i])] = i;
            }
            else
            {
                ins(0, 0, c, st[std::make_pair(x[i], y[i])], i - 1, x[i], y[i]);
                st.erase(std::make_pair(x[i], y[i]));
            }
        }
        for (auto [xy, in] : st)
            ins(0, 0, c, in, c-1, xy.first, xy.second);
    }

    //for (int i = 0; i < S; ++i) ds[i] = S;

    ds1 = dsu(n);
    ds1.savemode = 1;

    for (int i = 0; i < q; ++i)
        at[w[i]].emplace_back(i, p[i]);

    ans.resize(q);
    dfs(0, 0, c);

    return ans;
}

Compilation message (stderr)

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:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (int i = 0; i < t.size(); ++i)
      |                         ~~^~~~~~~~~~

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