답안 #66504 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66504	2018-08-11T05:59:27 Z	kingpig9	Collapse (JOI18_collapse)	C++11	100 / 100	3313 ms	21652 KB

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #66504

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 30.0 / 30.0

Subtask #4 35.0 / 35.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
30.0 / 30.0

Subtask #4
35.0 / 35.0