Submission #1159942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159942		Der_Vlapos	Collapse (JOI18_collapse)	C++20	35 / 100	1358 ms	23612 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()

struct DSU
{
	struct change
	{
		int x, px, szx, y, py, szy, cnt;
	};
	stack<change> changes;
	vector<int> p, sz;
	int cnt = 0;

	void init(int n)
	{
		cnt = n;
		p.resize(n);
		sz.resize(n);
		for (int i = 0; i < n; ++i)
		{
			sz[i] = 1;
			p[i] = i;
		}
	}

	int getR(int v)
	{
		return p[v] == v ? v : getR(p[v]);
	}

	void undo()
	{
		assert(changes.size());
		auto c = changes.top();
		changes.pop();
		cnt = c.cnt;
		p[c.x] = c.px;
		sz[c.x] = c.szx;
		p[c.y] = c.py;
		sz[c.y] = c.szy;
	}

	void merge(int a, int b)
	{
		a = getR(a);
		b = getR(b);

		changes.push({a, p[a], sz[a], b, p[b], sz[b], cnt});
		if (a == b)
			return;
		cnt--;
		if (sz[a] < sz[b])
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
};

struct segTree
{
	struct Node
	{
		vector<pii> segs;
		vector<int> qrs;
	};
	vector<Node> tree;
	DSU dsu;
	int sz = 0;

	void init(int n)
	{
		sz = 1;
		while (sz < n)
			sz *= 2;
		tree.resize(2 * sz);
	}

	void addQr(int pos, int id, int v, int lv, int rv)
	{
		if (rv - lv == 1)
		{
			tree[v].qrs.pb(id);
			return;
		}
		int m = (lv + rv) >> 1;
		if (pos < m)
			addQr(pos, id, v * 2 + 1, lv, m);
		else
			addQr(pos, id, v * 2 + 2, m, rv);
	}

	void addQr(int pos, int id)
	{
		addQr(pos, id, 0, 0, sz);
	}

	void addSeg(int l, int r, pii e, int v, int lv, int rv)
	{
		if (l <= lv and rv <= r)
		{
			tree[v].segs.push_back(e);
			return;
		}
		if (rv <= l or r <= lv)
			return;
		int m = (lv + rv) >> 1;
		addSeg(l, r, e, v * 2 + 1, lv, m);
		addSeg(l, r, e, v * 2 + 2, m, rv);
	}

	void addSeg(int l, int r, pii e)
	{
		addSeg(l, r, e, 0, 0, sz);
	}

	void traverse(vector<int> &ans, int v, int lv, int rv)
	{
		for (auto e : tree[v].segs)
		{
			dsu.merge(e.f, e.s);
		}

		// cerr << v << " " << lv << " " << rv << "WAT\n";
		if (rv - lv == 1)
		{
			for (auto id : tree[v].qrs)
				ans[id] = dsu.cnt;
		}
		int m = (lv + rv) >> 1;
		if (rv - lv > 1)
		{
			traverse(ans, v * 2 + 1, lv, m);
			traverse(ans, v * 2 + 2, m, rv);
		}

		for (int i = 0; i < tree[v].segs.size(); ++i)
		{
			auto e = tree[v].segs[i];
			dsu.undo();
		}
	}

	void traverse(vector<int> &ans)
	{
		traverse(ans, 0, 0, sz);
	}
};

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

	for (int i = 0; i < x.size(); ++i)
		if (x[i] > y[i])
			swap(x[i], y[i]);

	int m = x.size();
	if (m < 5e3 + 10 and n < 5e3 + 10 and q < 5e3 + 10)
	{
		for (int cq = 0; cq < q; ++cq)
		{
			set<pii> edges;
			for (int i = 0; i <= w[cq]; ++i)
				if (y[i] <= p[cq] or p[cq] + 1 <= x[i])
					if (t[i])
						edges.erase({x[i], y[i]});
					else
						edges.insert({x[i], y[i]});
			DSU dsu;
			dsu.init(n);
			for (auto [x, y] : edges)
			{
				assert(!(x <= p[cq] and p[cq] + 1 <= y));
				dsu.merge(x, y);
			}
			ans[cq] = dsu.cnt;
		}
	}
	else
	{
		int badP = p[0];

		vector<pii> qrs;
		for (int i = 0; i < q; ++i)
			qrs.pb({w[i], i});
		sort(all(qrs));

		vector<pair<pii, pii>> edges;

		int timer = 0;
		{
			int u = 0;
			set<pair<pii, int>> curEdges;
			for (int i = 0; i < m; ++i)
				if (y[i] <= badP or badP + 1 <= x[i])
				{
					while (u < q and qrs[u].f < i)
					{
						qrs[u].f = timer;
						u++;
					}
					timer++;
					if (t[i] == 0)
						curEdges.insert({{x[i], y[i]}, timer});
					else
					{
						auto it = curEdges.lower_bound({{x[i], y[i]}, -1});
						edges.pb({{x[i], y[i]}, {it->s, timer}});
						curEdges.erase(it);
					}
				}
			for (; u < q; ++u)
				qrs[u].f = timer;
			timer++;
			for (auto [e, st] : curEdges)
				edges.pb({e, {st, timer}});
		}

		segTree tree;
		tree.init(timer);
		tree.dsu.init(n);

		for (auto [t, id] : qrs)
			tree.addQr(t, id);
		for (auto [e, t] : edges)
			tree.addSeg(t.f, t.s, e);
		tree.traverse(ans);
	}

	return ans;
}

// #include "collapse.h"
// #include <cstdio>
// #include <cstdlib>

// int main(int argc, char *argv[])
// {
// 	int N, C, Q;
// 	scanf("%d%d%d", &N, &C, &Q);
// 	std::vector<int> T(C), X(C), Y(C);
// 	for (int i = 0; i < C; i++)
// 	{
// 		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
// 	}
// 	std::vector<int> W(Q), P(Q);
// 	for (int i = 0; i < Q; i++)
// 	{
// 		scanf("%d%d", &W[i], &P[i]);
// 	}
// 	auto res = simulateCollapse(N, T, X, Y, W, P);
// 	for (auto i : res)
// 	{
// 		printf("%d\n", i);
// 	}
// }

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