Submission #66193

#	Time	Username	Problem	Language	Result	Execution time	Memory
66193		kingpig9	Collapse (JOI18_collapse)	C++11	35 / 100	418 ms	99064 KiB

collapse

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, C, Q;

namespace subtask1 {
	const int MAXN = 5010;

	struct union_find {
		int par[100320];  //don't forget to init
		int ncomp;

		int find (int x) {
			return x == par[x] ? x : par[x] = find(par[x]);
		}

		bool merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return false;
			}
			par[x] = y;
			ncomp--;
			return true;
		}

		void reset (int sz) {
			for (int i = 0; i < sz; i++) {
				par[i] = i;
			}
			ncomp = sz;
		}
	};

	map<pii, int> mpind;
	bitset<MAXN> active[MAXN];
	union_find uf;

	vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
		for (int i = 0; i < C; i++) {
			if (i) {
				active[i] = active[i - 1];
			}

			int indxy;
			if (mpind.count(pii(X[i], Y[i]))) {
				indxy = mpind[pii(X[i], Y[i])];
			} else {
				indxy = mpind[pii(X[i], Y[i])] = i;
			}

			if (T[i] == 0) {
				active[i][indxy] = true;
			} else {
				active[i][indxy] = false;
			}
		}

		vector<int> ans;
		for (int i = 0; i < Q; i++) {
			uf.reset(N);
			//day W[i]
			for (int j = 0; j < C; j++) {
				if (active[W[i]][j]) {
					if (!(X[j] <= P[i] && P[i] + 1 <= Y[j])) {
						uf.merge(X[j], Y[j]);
						debug("avail %d %d\n", X[j], Y[j]);
					}
				}
			}

			debug("warm\n");
			ans.push_back(uf.ncomp);
		}

		return ans;
	}
}

//should have gotten this...too bad not enough time.
namespace subtask2 {
	const int MAXN = 1 << 17;

	struct union_find {
		int par[MAXN], sz[MAXN];    //don't forget to init
		int ncmp;
		pair<int*, int> stk[MAXN * 34];
		int stksz;

		void init (int n) {
			ncmp = n;
			for (int i = 0; i < n; i++) {
				par[i] = i;
				sz[i] = 1;
			}
			stksz = 0;
		}

		int find (int x) {
			return x == par[x] ? x : find(par[x]);
		}

		void change (int &x, int y) {
			stk[stksz++] = make_pair(&x, x);
			x = y;
		}

		void merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return;
			}
			if (sz[x] > sz[y]) {
				swap(x, y);
			}
			change(sz[y], sz[y] + sz[x]);
			change(par[x], y);
			change(ncmp, ncmp - 1);
		}

		void rollback (int s) {
			while (stksz > s) {
				auto p = stk[--stksz];
				*(p.fi) = p.se;
			}
		}
	};

	union_find uf;
	int seglt[2 * MAXN], segrt[2 * MAXN];
	vector<pii> tree[2 * MAXN];

	void update (int a, int b, pii v, int cur = 1) {
		int lt = seglt[cur], rt = segrt[cur];
		if (rt <= a || b <= lt) {
			return;
		}

		if (a <= lt && rt <= b) {
			tree[cur].push_back(v);
			return;
		}

		update(a, b, v, 2 * cur);
		update(a, b, v, 2 * cur + 1);
	}

	int P;
	int ncompt[MAXN];	//number of components at this time

	void calcseg (int cur = 1, int lt = 0, int rt = MAXN) {
		seglt[cur] = lt;
		segrt[cur] = rt;
		int mid = (lt + rt) >> 1;
		if (rt - lt > 1) {
			calcseg((cur << 1), lt, mid);
			calcseg((cur << 1) | 1, mid, rt);
		}
	}

	void dfs (int cur = 1) {
		int lt = seglt[cur], rt = segrt[cur];
		if (lt >= C) {
			return;
		}

		int state = uf.stksz;

		//add edges
		for (pii e : tree[cur]) {
			uf.merge(e.fi, e.se);
		}

		if (rt - lt == 1) {
			ncompt[lt] = uf.ncmp;
		} else {
			dfs(cur << 1);
			dfs((cur << 1) | 1);
		}

		uf.rollback(state);
	}

	vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, int ppppp) {
		uf.init(N);
		P = ppppp;
		map<pii, int> mp;
		calcseg();

		for (int i = 0; i < C; i++) {
			pii e(X[i], Y[i]);
			if (X[i] <= P && P + 1 <= Y[i]) {
				continue;
			}
			if (mp.count(e)) {
				update(mp.at(e), i, e);
				mp.erase(e);
			} else {
				mp[e] = i;
			}
		}
		debug("here\n");

		for (auto it : mp) {
			update(it.se, C, it.fi);
		}

		//ok let's go!
		dfs();

		vector<int> ans;
		for (int day : W) {
			ans.push_back(ncompt[day]);
		}
		return ans;
	}
}

namespace subtask3 {
	const int MAXN = 1e5 + 320;
	const int SQRT = 320;
	//6s, 512MB

	struct union_find {
		int par[MAXN];
		vector<pair<int*, int>> chng;
		bool active;
		int ncomp;

		void reset() {
			for (int i = 0; i < N; i++) {
				par[i] = i;
			}
			ncomp = N;
			chng.clear();
			active = false;
		}

		void change (int &x, int y) {
			if (active) {
				chng.push_back(make_pair(&x, x));
			}
			x = y;
		}

		int find (int x) {
			if (x == par[x]) {
				return x;
			}
			change(par[x], find(par[x]));
			return par[x];
		}

		void merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return;
			}
			change(par[x], y);
			change(ncomp, ncomp - 1);
		}

		void rollback() {
			for (auto p : chng) {
				*(p.fi) = p.se;
			}
			chng.clear();
		}
	};

	vector<pii> queries[MAXN];	//queries[day] = vector(position, id)
	int ans[MAXN];
	union_find uf;
	pii estl[MAXN], estr[MAXN], tmp[MAXN];

	bool cmpr (pii p1, pii p2) {
		return p1.se < p2.se;
	}

	bool cmpl (pii p1, pii p2) {
		return p1.fi > p2.fi;
	}

	vector<int> go (vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
		//X, Y = roads constructed
		//w, P = questions.
		for (int i = 0; i < Q; i++) {
			queries[W[i]].push_back({P[i], i});
		}

		for (int sday = 0; sday < C; sday += SQRT) {
			int eday = min(sday + SQRT, C);
			//what is the stuff before sday? certainly need to add this in.
			vector<array<int, 3>> vqu;
			for (int i = sday; i < eday; i++) {
				for (pii p : queries[i]) {
					vqu.push_back({p.fi, i, p.se});
				}
			}

			//ok let's now go to this now.

			int posr = 0;	//position of estr
			//prefix
			debug("-------start prefix----------\n");
			
			sort(all(vqu));
			uf.reset();
			for (auto q : vqu) {
				int pos = q[0];
				for (; posr < sday && estr[posr].se <= q[0]; posr++) {
					uf.merge(estr[posr].fi, estr[posr].se);
					debug("merge %d %d\n", estr[posr].fi, estr[posr].se);
				}

				//need this
				for (int i = sday; i < eday; i++) {
					uf.find(X[i]);
					uf.find(Y[i]);
				}

				uf.active = true;
				debug("--active--\n");
				//then merge the rest of them!
				for (int i = sday; i <= q[1]; i++) {
					//is this a valid merge?
					if (Y[i] <= pos) {
						uf.merge(X[i], Y[i]);
						debug("merge %d %d\n", X[i], Y[i]);
					}
				}

				ans[q[2]] += uf.ncomp;
				debug("answer[%d] += %d\n", q[2], uf.ncomp);
				uf.rollback();
				uf.active = false;
				debug("--inactive--\n");
			}

			debug("-------start suffix----------\n");
			//suffix

			uf.reset();
			reverse(all(vqu));

			int posl = 0;
			for (auto q : vqu) {
				int pos = q[0];
				//note: strictly greater than q[0]
				for (; posl < sday && estl[posl].fi > q[0]; posl++) {
					uf.merge(estl[posl].fi, estl[posl].se);
					debug("merge %d %d\n", estl[posl].fi, estl[posl].se);
				}
				//need this
				for (int i = sday; i < eday; i++) {
					uf.find(X[i]);
					uf.find(Y[i]);
				}

				debug("--active--\n");
				uf.active = true;
				for (int i = sday; i <= q[1]; i++) {
					if (X[i] > pos) {
						uf.merge(X[i], Y[i]);
						debug("merge %d %d\n", X[i], Y[i]);
					}
				}

				ans[q[2]] += uf.ncomp - N;
				debug("answer[%d] += %d; answer[%d] -= N\n", q[2], uf.ncomp, q[2]);
				uf.rollback();
				debug("--inactive--\n");
				uf.active = false;
			}


			//then add the new edges
			vector<pii> nedge;
			for (int i = sday; i < eday; i++) {
				nedge.push_back({X[i], Y[i]});
			}
			sort(all(nedge), cmpl);
			copy(tmp, merge(estl, estl + sday, all(nedge), tmp, cmpl), estl);
			sort(all(nedge), cmpr);
			copy(tmp, merge(estr, estr + sday, all(nedge), tmp, cmpr), estr);
		}
		return vector<int> (ans, ans + Q);
	}
}

vector<int> simulateCollapse (int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	N = n;
	C = X.size();
	Q = W.size();

	for (int i = 0; i < C; i++) {
		if (X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
	}

	if (N <= 5000 && Q <= 5000) {
		return subtask1::go(T, X, Y, W, P);
	} else if ((set<int> (all(P))).size() == 1) {
		return subtask2::go(T, X, Y, W, P[0]);
	} else if (count(all(T), 0) == T.size()) {
		return subtask3::go(X, Y, W, P);
	}
}

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:421:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if (count(all(T), 0) == T.size()) {
             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:424:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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