Submission #101781

#	Time	Username	Problem	Language	Result	Execution time	Memory
101781		KCSC	Collapse (JOI18_collapse)	C++14	100 / 100	3849 ms	27292 KiB

collapse

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

const int DIM = 100005;
const int SIZE = 305;

struct Edge {
	int x, y, t1, t2;
	
	Edge(int _x, int _y, int _t1, int _t2) :
		x(_x), y(_y), t1(_t1), t2(_t2) {}

	bool operator <(const Edge &other) const {
		return (*this).y < other.y; }
};

struct Query {
	int p, t, id;

	Query(int _p, int _t, int _id) :
		p(_p), t(_t), id(_id) {}

	bool operator <(const Query &other) const {
		return (*this).p < other.p; }
};

struct UndoDSU {
	int cnt, siz;
	int fth[DIM], lst[DIM], szt[DIM];

	UndoDSU(int _siz = DIM - 1) : 
		cnt(0), siz(_siz) {}

	inline void initialize(void) {
		cnt = 0;
		for (int i = 1; i <= siz; ++i) {
			fth[i] = i; szt[i] = 1; } }

	inline int getRoot(int x) {
		while (fth[x] != x) {
			x = fth[x]; }
		return x; }

	bool unite(int x, int y) {
		x = getRoot(x); y = getRoot(y);
		if (szt[x] < szt[y]) {
			swap(x, y); }
		if (x != y) {
			lst[++cnt] = y; szt[x] += szt[y]; fth[y] = x;
			return true; }
		else {
			return false; } }

	void undo(int nr) {
		assert(nr <= cnt);
		for (; cnt > nr; --cnt) {
			int y = lst[cnt], x = fth[y];
			szt[x] -= szt[y]; fth[y] = y; } }
};

void solve(int n, int m, int t, int k, 
	vector<Edge> &edg, vector<Query> &qry, vector<int> &ans) {
	
	UndoDSU dsu(n); vector<Query> lst[DIM]; vector<Edge> all, psb;

	for (auto it : qry) {
		lst[it.t / SIZE * SIZE].push_back(it); }
	for (int i = 0; i <= m; i += SIZE) {
		dsu.initialize(); all.clear(); psb.clear();
		for (auto it : edg) {
			if (it.t1 <= i and it.t2 >= i + SIZE - 1) {
				all.push_back(it); }
			else if (it.t2 >= i and it.t1 <= i + SIZE - 1) {
				psb.push_back(it); } }
		sort(all.begin(), all.end()); 
		sort(lst[i].begin(), lst[i].end());
		int ptx = 0;
		for (auto qr : lst[i]) {
			for (; ptx < all.size() and all[ptx].y <= qr.p; ++ptx) {
				dsu.unite(all[ptx].x, all[ptx].y); }
			int cnt = dsu.cnt;
			for (auto it : psb) {
				if (it.y <= qr.p and it.t1 <= qr.t and qr.t <= it.t2) {
					dsu.unite(it.x, it.y); } }
			ans[qr.id] -= dsu.cnt; dsu.undo(cnt); } } }
	

vector<int> simulateCollapse(int n, 
	vector<int> _typ, vector<int> _crd1, vector<int> _crd2,
	vector<int> _tim, vector<int> _plc) {

	const int m = (int) _typ.size(), k = (int) _tim.size();
	vector<int> ans(k, n); vector<Edge> edg; vector<Query> qry;
	map<pair<int, int>, int> mmp;

	for (int i = 1; i <= m; ++i) {
		int x =_crd1[i - 1], y = _crd2[i - 1];
		if (++x > ++y) {
			swap(x, y); }
		if (_typ[i - 1] == 0) {
			mmp[make_pair(x, y)] = i; }
		else {
			edg.push_back(Edge(x, y, mmp[make_pair(x, y)], i - 1)); 
			mmp.erase(mmp.find(make_pair(x, y))); } }
	for (auto it : mmp) {
		int x, y; tie(x, y) = it.first;
		edg.push_back(Edge(x, y, it.second, m)); } 
	for (int i = 1; i <= k; ++i) {
		int p = _plc[i - 1] + 1, t = _tim[i - 1] + 1;
		qry.push_back(Query(p, t, i - 1)); }
	solve(n, m, edg.size(), k, edg, qry, ans);
	for (auto &it : edg) {
		it.x = n - it.x + 1, it.y = n - it.y + 1;
		swap(it.x, it.y); }
	for (auto &it : qry) {
		it.p = n - it.p; }
	solve(n, m, edg.size(), k, edg, qry, ans);
	return ans; }

#ifdef HOME
int main(void) {
	freopen("collapse.in", "r", stdin);
	freopen("collapse.out", "w", stdout);
	int n, c, q; cin >> n >> c >> q;
	vector<int> t(c, 0), x(c, 0), y(c, 0), w(q, 0), p(q, 0);
	for (int i = 0; i < c; ++i) {
		cin >> t[i] >> x[i] >> y[i]; }
	for (int i = 0; i < q; ++i) {
		cin >> w[i] >> p[i]; }
	vector<int> ans = simulateCollapse(n, t, x, y, w, p);
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\n"; }
	return 0; }
#endif

Compilation message (stderr)

collapse.cpp: In function 'void solve(int, int, int, int, std::vector<Edge>&, std::vector<Query>&, std::vector<int>&)':
collapse.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (; ptx < all.size() and all[ptx].y <= qr.p; ++ptx) {
           ~~~~^~~~~~~~~~~~

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