Submission #59392

#	Time	Username	Problem	Language	Result	Execution time	Memory
59392		kingpig9	Collapse (JOI18_collapse)	C++11	0 / 100	15091 ms	19316 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;

struct union_find {
	int par[100010];  //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;
	}
};

namespace subtask1 {
	const int MAXN = 5010;

	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;
		stack<pair<int*, int>> stk;

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

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

		void change (int &x, int y) {
			stk.push(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 (stk.size() > s) {
				pair<int*, int> p = stk.top();
				stk.pop();
				*(p.fi) = p.se;
			}
		}
	};

	union_find ufl, ufr;
	vector<pii> tree[2 * MAXN];

	void update (int a, int b, pii v, int cur = 1, int lt = 0, int rt = MAXN) {
		if (rt <= a || b <= lt) {
			return;
		}

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

		int mid = (lt + rt) / 2;
		update(a, b, v, 2 * cur, lt, mid);
		update(a, b, v, 2 * cur + 1, mid, rt);
	}

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

	void dfs (int cur = 1, int lt = 0, int rt = MAXN) {
		if (lt >= C) {
			return;
		}

		int statel = ufl.stk.size(), stater = ufr.stk.size();

		//add edges
		for (pii e : tree[cur]) {
			if (e.se <= P) {
				ufl.merge(e.fi, e.se);
			} else if (e.fi > P) {
				ufr.merge(e.fi, e.se);
			}
		}

		if (rt - lt == 1) {
			ncompt[lt] = ufl.ncmp + ufr.ncmp - N;	//minus N -- we both initted to N.
		} else {
			int mid = (lt + rt) / 2;
			dfs(2 * cur, lt, mid);
			dfs(2 * cur + 1, mid, rt);
		}

		ufl.rollback(statel);
		ufr.rollback(stater);
	}

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

		for (int i = 0; i < C; i++) {
			pii e(X[i], Y[i]);
			if (mp.count(e)) {
				update(mp.at(e), i, e);
				mp.erase(e);
			} else {
				mp[e] = i;
			}
		}

		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 {
	//6s, 512MB

	struct query {
		int day, pos;	//which day? which position?
		int id;	//what is the index?
	};

	bool operator < (query q1, query q2) {
		return q1.day < q2.day;
	}

	const int MAXN = 1e5 + 320;
	const int SQRT = 320;
	union_find uf[SQRT];
	int qid[SQRT];
	vector<pii> edges;
	vector<query> qu;
	int ans[MAXN];

	vector<int> go (vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
		for (int i = 0; i < Q; i++) {
			qu.push_back((query) {W[i], P[i], i});
		}
		sort(all(qu));

		for (int i = 0; i < Q; i += SQRT) {
			//i to i + Q.
			int nq = 0;
			for (int j = i; j < Q && j < i + SQRT; j++) {
				//let's add this query in
				uf[j - i].reset(N);
				nq++;
			}

			//construction plan in this day
			int cday = 0;
			for (int j = i; j < Q && j < i + SQRT; j++) {
				int day = qu[j].day;
				for (; cday <= day; cday++) {
					//let's add this day in to ALL of 'em
					for (int k = 0; k < nq; k++) {
						if (!(X[cday] <= qu[j].pos && qu[j].pos + 1 <= Y[cday])) {
							uf[k].merge(X[cday], Y[cday]);
						}
					}
				}

				//ok let's now query this one!
				ans[qu[j].id] = uf[j - i].ncomp;
			}
		}
		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 (count(all(T), 0) == T.size()) {
		return subtask3::go(X, Y, W, P);
	} else 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]);
	}
}

Compilation message (stderr)

collapse.cpp: In member function 'void subtask2::union_find::rollback(int)':
collapse.cpp:134:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (stk.size() > s) {
           ~~~~~~~~~~~^~~
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:289:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (count(all(T), 0) == T.size()) {
      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:296:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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