oj.uz

Submission #66161

# Submission time Handle Problem Language Result Execution time Memory
66161 2018-08-09T22:51:29 Z kingpig9 Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 159376 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 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
	int seglt[2 * MAXN], segrt[2 * MAXN], segmid[2 * MAXN];

	void calcseg (int cur = 1, int lt = 0, int rt = MAXN) {
		seglt[cur] = lt;
		segrt[cur] = rt;
		int mid = (lt + rt) >> 1;
		segmid[cur] = mid;
		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 statel = ufl.stksz, stater = ufr.stksz;

		//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 {
			dfs(cur << 1);
			dfs((cur << 1) | 1);
		}

		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 (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!
		calcseg();
		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:308:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if (count(all(T), 0) == T.size()) {
             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:313: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 171 ms 149496 KB Output is correct
2 Correct 116 ms 149496 KB Output is correct
3 Correct 117 ms 149496 KB Output is correct
4 Correct 114 ms 149496 KB Output is correct
5 Correct 174 ms 149876 KB Output is correct
6 Correct 305 ms 150048 KB Output is correct
7 Correct 142 ms 150048 KB Output is correct
8 Correct 139 ms 150048 KB Output is correct
9 Correct 189 ms 150048 KB Output is correct
10 Correct 288 ms 150048 KB Output is correct
11 Correct 368 ms 150180 KB Output is correct
12 Correct 488 ms 150180 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 152124 KB Output is correct
2 Correct 155 ms 152124 KB Output is correct
3 Correct 230 ms 158376 KB Output is correct
4 Correct 181 ms 158376 KB Output is correct
5 Correct 249 ms 159376 KB Output is correct
6 Correct 1935 ms 159376 KB Output is correct
7 Execution timed out 15111 ms 159376 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 159376 KB Output is correct
2 Incorrect 168 ms 159376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 149496 KB Output is correct
2 Correct 116 ms 149496 KB Output is correct
3 Correct 117 ms 149496 KB Output is correct
4 Correct 114 ms 149496 KB Output is correct
5 Correct 174 ms 149876 KB Output is correct
6 Correct 305 ms 150048 KB Output is correct
7 Correct 142 ms 150048 KB Output is correct
8 Correct 139 ms 150048 KB Output is correct
9 Correct 189 ms 150048 KB Output is correct
10 Correct 288 ms 150048 KB Output is correct
11 Correct 368 ms 150180 KB Output is correct
12 Correct 488 ms 150180 KB Output is correct
13 Correct 146 ms 152124 KB Output is correct
14 Correct 155 ms 152124 KB Output is correct
15 Correct 230 ms 158376 KB Output is correct
16 Correct 181 ms 158376 KB Output is correct
17 Correct 249 ms 159376 KB Output is correct
18 Correct 1935 ms 159376 KB Output is correct
19 Execution timed out 15111 ms 159376 KB Time limit exceeded
20 Halted 0 ms 0 KB -