oj.uz

Submission #66159

# Submission time Handle Problem Language Result Execution time Memory
66159 2018-08-09T22:23:51 Z kingpig9 Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 165248 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 (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:305:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if (count(all(T), 0) == T.size()) {
             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:310: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 175 ms 149496 KB Output is correct
2 Correct 118 ms 149496 KB Output is correct
3 Correct 119 ms 149496 KB Output is correct
4 Correct 120 ms 149496 KB Output is correct
5 Correct 180 ms 149552 KB Output is correct
6 Correct 301 ms 149824 KB Output is correct
7 Correct 134 ms 149824 KB Output is correct
8 Correct 134 ms 149824 KB Output is correct
9 Correct 184 ms 149900 KB Output is correct
10 Correct 265 ms 149916 KB Output is correct
11 Correct 378 ms 150004 KB Output is correct
12 Correct 473 ms 150064 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 152140 KB Output is correct
2 Correct 133 ms 152140 KB Output is correct
3 Correct 263 ms 161884 KB Output is correct
4 Correct 175 ms 161884 KB Output is correct
5 Correct 246 ms 165248 KB Output is correct
6 Correct 1699 ms 165248 KB Output is correct
7 Execution timed out 15078 ms 165248 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 165248 KB Output is correct
2 Incorrect 154 ms 165248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 149496 KB Output is correct
2 Correct 118 ms 149496 KB Output is correct
3 Correct 119 ms 149496 KB Output is correct
4 Correct 120 ms 149496 KB Output is correct
5 Correct 180 ms 149552 KB Output is correct
6 Correct 301 ms 149824 KB Output is correct
7 Correct 134 ms 149824 KB Output is correct
8 Correct 134 ms 149824 KB Output is correct
9 Correct 184 ms 149900 KB Output is correct
10 Correct 265 ms 149916 KB Output is correct
11 Correct 378 ms 150004 KB Output is correct
12 Correct 473 ms 150064 KB Output is correct
13 Correct 143 ms 152140 KB Output is correct
14 Correct 133 ms 152140 KB Output is correct
15 Correct 263 ms 161884 KB Output is correct
16 Correct 175 ms 161884 KB Output is correct
17 Correct 246 ms 165248 KB Output is correct
18 Correct 1699 ms 165248 KB Output is correct
19 Execution timed out 15078 ms 165248 KB Time limit exceeded
20 Halted 0 ms 0 KB -