oj.uz

Submission #66165

# Submission time Handle Problem Language Result Execution time Memory
66165 2018-08-09T23:03:01 Z kingpig9 Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 88472 KB 
#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_findr {
		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_findr 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;
			}
		}

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

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 79736 KB Output is correct
2 Correct 69 ms 79736 KB Output is correct
3 Correct 69 ms 79736 KB Output is correct
4 Correct 61 ms 79736 KB Output is correct
5 Correct 120 ms 80060 KB Output is correct
6 Correct 249 ms 80336 KB Output is correct
7 Correct 81 ms 80336 KB Output is correct
8 Correct 90 ms 80336 KB Output is correct
9 Correct 129 ms 80336 KB Output is correct
10 Correct 201 ms 80336 KB Output is correct
11 Correct 351 ms 80512 KB Output is correct
12 Correct 424 ms 80512 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 82420 KB Output is correct
2 Correct 88 ms 82420 KB Output is correct
3 Correct 145 ms 87576 KB Output is correct
4 Correct 114 ms 87576 KB Output is correct
5 Correct 186 ms 88472 KB Output is correct
6 Correct 1808 ms 88472 KB Output is correct
7 Execution timed out 15027 ms 88472 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 88472 KB Output is correct
2 Incorrect 102 ms 88472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 79736 KB Output is correct
2 Correct 69 ms 79736 KB Output is correct
3 Correct 69 ms 79736 KB Output is correct
4 Correct 61 ms 79736 KB Output is correct
5 Correct 120 ms 80060 KB Output is correct
6 Correct 249 ms 80336 KB Output is correct
7 Correct 81 ms 80336 KB Output is correct
8 Correct 90 ms 80336 KB Output is correct
9 Correct 129 ms 80336 KB Output is correct
10 Correct 201 ms 80336 KB Output is correct
11 Correct 351 ms 80512 KB Output is correct
12 Correct 424 ms 80512 KB Output is correct
13 Correct 88 ms 82420 KB Output is correct
14 Correct 88 ms 82420 KB Output is correct
15 Correct 145 ms 87576 KB Output is correct
16 Correct 114 ms 87576 KB Output is correct
17 Correct 186 ms 88472 KB Output is correct
18 Correct 1808 ms 88472 KB Output is correct
19 Execution timed out 15027 ms 88472 KB Time limit exceeded
20 Halted 0 ms 0 KB -