oj.uz

Submission #66504

# Submission time Handle Problem Language Result Execution time Memory
66504 2018-08-11T05:59:27 Z kingpig9 Collapse (JOI18_collapse) C++11
100 / 100
 3313 ms 21652 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;
const int MAXN = 1e5 + 160;
const int SQRT = 320;

//#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;
int T[MAXN], X[MAXN], Y[MAXN];	//Edges
int E[MAXN];	//edge ID.
int W[MAXN], P[MAXN];	//Queries
int ans[MAXN];

struct union_find {
	int par[MAXN];
	stack<pair<int*, int>> chng;	//god fucking damn it. used vector not stack. Then used a "forall" loop on it. But you need to go backward NOT forward iterating through this container!!!
	bool active;
	int ncomp;

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

	void change (int &x, int y) {
		if (active) {
			chng.push(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() {
		while (!chng.empty()) {
			*(chng.top().fi) = chng.top().se;
			chng.pop();
		}
	}
};

int death[MAXN];	//death time of edge.
vector<pii> queries[MAXN];	//queries[day] = vector(position, id)
union_find uf;
int estl[MAXN], estr[MAXN], tmp[MAXN];

bool cmpr (int a, int b) {
	return Y[a] < Y[b];
}

bool cmpl (int a, int b) {
	return X[a] > X[b];
}

void solve() {
	//X, Y = roads constructed
	//w, P = questions.
	/*
	//they aren't vectors but global arrays.
	assert(X.size() == C);
	assert(Y.size() == C);
	assert(W.size() == Q);
	assert(P.size() == Q);
	*/

	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();

		//preliminary add edge if: it is born before sday (edgeid < sday) and if it dies >= eday (death[edgeid] >= eday)
		for (auto q : vqu) {
			int pos = q[0];
			for (; posr < sday && Y[estr[posr]] <= q[0]; posr++) {
				int edgeid = estr[posr];
				debug("Consider edge (%d, %d). death[%d] = %d. eday = %d\n", X[estr[posr]], Y[estr[posr]], edgeid, death[edgeid], eday);
				//assert(death[edgeid] >= eday);
				if (edgeid < sday && death[edgeid] >= eday) {
					uf.merge(X[edgeid], Y[edgeid]);
					debug("Rsection merge %d %d\n", X[edgeid], Y[edgeid]);
				}
			}

			//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 < eday; i++) {
				//aggh - need to actually loop through ALL of [sday, eday)...
				//is this a valid merge?
				debug("Start with ncomp = %d. i = %d\n", uf.ncomp, i);
				if (Y[i] <= pos) {
					//debug("find(1) == find(56)? %d. find(60) == find(72)? %d.\n", (uf.find(1) == uf.find(56)), (uf.find(60) == uf.find(72)));	//this is for the specific test data in "cbad.in" - it gets 36 not 35 in original buggy code for the first query (35 is correct answer)

					//only add edge if: born <= q[1] (edgeid <= q[1]) -- this is actually 100% going to happen here -- and not dead yet (death[edgeid] > q[1])
					int edgeid = E[i];
					debug("EID %d. Need it to be alive at day %d.\n", edgeid, q[1]);
					if (edgeid <= q[1] && death[edgeid] > q[1]) {
						uf.merge(X[i], Y[i]);
						debug("Lsection 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 && X[estl[posl]] > q[0]; posl++) {
				int edgeid = estl[posl];
				if (edgeid < sday && death[edgeid] >= eday) {
					uf.merge(X[edgeid], Y[edgeid]);
					debug("merge %d %d\n", X[edgeid], Y[edgeid]);
				}

			}
			//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 < eday; i++) {
				//aggh - need to actually loop through ALL of [sday, eday)...
				if (X[i] > pos) {
					//only add edge if: born <= q[1] (edgeid <= q[1]) -- this is actually 100% going to happen here -- and not dead yet (death[edgeid] > q[1])
					int edgeid = E[i];
					if (edgeid <= q[1] && death[edgeid] > q[1]) {
						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<int> nedge;
		for (int i = sday; i < eday; i++) {
			nedge.push_back(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);
	}
}

vector<int> simulateCollapse (int n, vector<int> ttt, vector<int> xxx, vector<int> yyy, vector<int> www, vector<int> ppp) {
	//globalize the variables
	N = n;
	C = xxx.size();
	Q = www.size();
	for (int i = 0; i < C; i++) {
		T[i] = ttt[i];
		X[i] = xxx[i];
		Y[i] = yyy[i];
	}
	for (int i = 0; i < Q; i++) {
		W[i] = www[i];
		P[i] = ppp[i];
	}

	map<pii, int> mpind;
	for (int i = 0; i < C; i++) {
		if (X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
		pii p(X[i], Y[i]);
		if (T[i] == 1) {
			//remove it
			int ind = mpind.at(p);
			death[ind] = i;
			debug("death (%d, %d) is %d. ind = %d --> death[%d] = %d\n", X[ind], Y[ind], i, ind, ind, i);
			E[i] = ind;
			mpind.erase(p);
		} else {
			death[i] = C;
			E[i] = i;
			mpind[p] = i;
		}
	}

	for (int i = 0; i < 6; i++) {
		debug("death[%d] = %d\n", i, death[i]);
	}

	solve();
	return vector<int> (ans, ans + Q);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3320 KB Output is correct
2 Correct 10 ms 3320 KB Output is correct
3 Correct 12 ms 3320 KB Output is correct
4 Correct 13 ms 3320 KB Output is correct
5 Correct 26 ms 3500 KB Output is correct
6 Correct 49 ms 3712 KB Output is correct
7 Correct 9 ms 3712 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct
9 Correct 28 ms 3712 KB Output is correct
10 Correct 61 ms 3712 KB Output is correct
11 Correct 52 ms 3856 KB Output is correct
12 Correct 64 ms 3904 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 8456 KB Output is correct
2 Correct 51 ms 8456 KB Output is correct
3 Correct 545 ms 14692 KB Output is correct
4 Correct 116 ms 14692 KB Output is correct
5 Correct 756 ms 14940 KB Output is correct
6 Correct 556 ms 14940 KB Output is correct
7 Correct 1159 ms 21248 KB Output is correct
8 Correct 694 ms 21248 KB Output is correct
9 Correct 59 ms 21248 KB Output is correct
10 Correct 75 ms 21248 KB Output is correct
11 Correct 490 ms 21248 KB Output is correct
12 Correct 795 ms 21248 KB Output is correct
13 Correct 1129 ms 21248 KB Output is correct
14 Correct 1152 ms 21444 KB Output is correct
15 Correct 1277 ms 21652 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 21652 KB Output is correct
2 Correct 67 ms 21652 KB Output is correct
3 Correct 100 ms 21652 KB Output is correct
4 Correct 143 ms 21652 KB Output is correct
5 Correct 625 ms 21652 KB Output is correct
6 Correct 684 ms 21652 KB Output is correct
7 Correct 1496 ms 21652 KB Output is correct
8 Correct 2616 ms 21652 KB Output is correct
9 Correct 66 ms 21652 KB Output is correct
10 Correct 631 ms 21652 KB Output is correct
11 Correct 2786 ms 21652 KB Output is correct
12 Correct 2963 ms 21652 KB Output is correct
13 Correct 2986 ms 21652 KB Output is correct
14 Correct 3313 ms 21652 KB Output is correct
15 Correct 2977 ms 21652 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3320 KB Output is correct
2 Correct 10 ms 3320 KB Output is correct
3 Correct 12 ms 3320 KB Output is correct
4 Correct 13 ms 3320 KB Output is correct
5 Correct 26 ms 3500 KB Output is correct
6 Correct 49 ms 3712 KB Output is correct
7 Correct 9 ms 3712 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct
9 Correct 28 ms 3712 KB Output is correct
10 Correct 61 ms 3712 KB Output is correct
11 Correct 52 ms 3856 KB Output is correct
12 Correct 64 ms 3904 KB Output is correct
13 Correct 45 ms 8456 KB Output is correct
14 Correct 51 ms 8456 KB Output is correct
15 Correct 545 ms 14692 KB Output is correct
16 Correct 116 ms 14692 KB Output is correct
17 Correct 756 ms 14940 KB Output is correct
18 Correct 556 ms 14940 KB Output is correct
19 Correct 1159 ms 21248 KB Output is correct
20 Correct 694 ms 21248 KB Output is correct
21 Correct 59 ms 21248 KB Output is correct
22 Correct 75 ms 21248 KB Output is correct
23 Correct 490 ms 21248 KB Output is correct
24 Correct 795 ms 21248 KB Output is correct
25 Correct 1129 ms 21248 KB Output is correct
26 Correct 1152 ms 21444 KB Output is correct
27 Correct 1277 ms 21652 KB Output is correct
28 Correct 48 ms 21652 KB Output is correct
29 Correct 67 ms 21652 KB Output is correct
30 Correct 100 ms 21652 KB Output is correct
31 Correct 143 ms 21652 KB Output is correct
32 Correct 625 ms 21652 KB Output is correct
33 Correct 684 ms 21652 KB Output is correct
34 Correct 1496 ms 21652 KB Output is correct
35 Correct 2616 ms 21652 KB Output is correct
36 Correct 66 ms 21652 KB Output is correct
37 Correct 631 ms 21652 KB Output is correct
38 Correct 2786 ms 21652 KB Output is correct
39 Correct 2963 ms 21652 KB Output is correct
40 Correct 2986 ms 21652 KB Output is correct
41 Correct 3313 ms 21652 KB Output is correct
42 Correct 2977 ms 21652 KB Output is correct
43 Correct 939 ms 21652 KB Output is correct
44 Correct 1925 ms 21652 KB Output is correct
45 Correct 929 ms 21652 KB Output is correct
46 Correct 2617 ms 21652 KB Output is correct
47 Correct 62 ms 21652 KB Output is correct
48 Correct 75 ms 21652 KB Output is correct
49 Correct 627 ms 21652 KB Output is correct
50 Correct 747 ms 21652 KB Output is correct
51 Correct 1117 ms 21652 KB Output is correct
52 Correct 1375 ms 21652 KB Output is correct
53 Correct 1693 ms 21652 KB Output is correct
54 Correct 1664 ms 21652 KB Output is correct
55 Correct 1905 ms 21652 KB Output is correct
56 Correct 2296 ms 21652 KB Output is correct
57 Correct 2860 ms 21652 KB Output is correct
58 Correct 2454 ms 21652 KB Output is correct
59 Correct 2676 ms 21652 KB Output is correct
60 Correct 2864 ms 21652 KB Output is correct