답안 #66503 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66503	2018-08-11T05:53:46 Z	kingpig9	Collapse (JOI18_collapse)	C++11	100 / 100	3216 ms	60608 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++) {
				//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++) {
				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, vector<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).back();
			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.at(p).pop_back();
		} else {
			death[i] = C;
			E[i] = i;
			mpind[p].push_back(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	16 ms	3320 KB	Output is correct
2	Correct	9 ms	3320 KB	Output is correct
3	Correct	10 ms	3320 KB	Output is correct
4	Correct	12 ms	3332 KB	Output is correct
5	Correct	28 ms	3448 KB	Output is correct
6	Correct	53 ms	4008 KB	Output is correct
7	Correct	7 ms	4008 KB	Output is correct
8	Correct	9 ms	4008 KB	Output is correct
9	Correct	29 ms	4008 KB	Output is correct
10	Correct	49 ms	4008 KB	Output is correct
11	Correct	59 ms	4100 KB	Output is correct
12	Correct	67 ms	4244 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	8524 KB	Output is correct
2	Correct	67 ms	8524 KB	Output is correct
3	Correct	560 ms	14780 KB	Output is correct
4	Correct	110 ms	14780 KB	Output is correct
5	Correct	680 ms	15396 KB	Output is correct
6	Correct	610 ms	15396 KB	Output is correct
7	Correct	1275 ms	25764 KB	Output is correct
8	Correct	684 ms	25764 KB	Output is correct
9	Correct	52 ms	25764 KB	Output is correct
10	Correct	80 ms	25764 KB	Output is correct
11	Correct	493 ms	25764 KB	Output is correct
12	Correct	875 ms	25764 KB	Output is correct
13	Correct	1161 ms	25764 KB	Output is correct
14	Correct	1192 ms	26156 KB	Output is correct
15	Correct	1258 ms	26316 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	26316 KB	Output is correct
2	Correct	72 ms	26316 KB	Output is correct
3	Correct	100 ms	26316 KB	Output is correct
4	Correct	157 ms	26316 KB	Output is correct
5	Correct	638 ms	26316 KB	Output is correct
6	Correct	711 ms	26316 KB	Output is correct
7	Correct	1589 ms	26316 KB	Output is correct
8	Correct	2666 ms	26316 KB	Output is correct
9	Correct	65 ms	26316 KB	Output is correct
10	Correct	634 ms	26316 KB	Output is correct
11	Correct	2800 ms	26316 KB	Output is correct
12	Correct	2919 ms	26316 KB	Output is correct
13	Correct	3216 ms	26316 KB	Output is correct
14	Correct	3100 ms	26316 KB	Output is correct
15	Correct	3111 ms	26316 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	3320 KB	Output is correct
2	Correct	9 ms	3320 KB	Output is correct
3	Correct	10 ms	3320 KB	Output is correct
4	Correct	12 ms	3332 KB	Output is correct
5	Correct	28 ms	3448 KB	Output is correct
6	Correct	53 ms	4008 KB	Output is correct
7	Correct	7 ms	4008 KB	Output is correct
8	Correct	9 ms	4008 KB	Output is correct
9	Correct	29 ms	4008 KB	Output is correct
10	Correct	49 ms	4008 KB	Output is correct
11	Correct	59 ms	4100 KB	Output is correct
12	Correct	67 ms	4244 KB	Output is correct
13	Correct	46 ms	8524 KB	Output is correct
14	Correct	67 ms	8524 KB	Output is correct
15	Correct	560 ms	14780 KB	Output is correct
16	Correct	110 ms	14780 KB	Output is correct
17	Correct	680 ms	15396 KB	Output is correct
18	Correct	610 ms	15396 KB	Output is correct
19	Correct	1275 ms	25764 KB	Output is correct
20	Correct	684 ms	25764 KB	Output is correct
21	Correct	52 ms	25764 KB	Output is correct
22	Correct	80 ms	25764 KB	Output is correct
23	Correct	493 ms	25764 KB	Output is correct
24	Correct	875 ms	25764 KB	Output is correct
25	Correct	1161 ms	25764 KB	Output is correct
26	Correct	1192 ms	26156 KB	Output is correct
27	Correct	1258 ms	26316 KB	Output is correct
28	Correct	92 ms	26316 KB	Output is correct
29	Correct	72 ms	26316 KB	Output is correct
30	Correct	100 ms	26316 KB	Output is correct
31	Correct	157 ms	26316 KB	Output is correct
32	Correct	638 ms	26316 KB	Output is correct
33	Correct	711 ms	26316 KB	Output is correct
34	Correct	1589 ms	26316 KB	Output is correct
35	Correct	2666 ms	26316 KB	Output is correct
36	Correct	65 ms	26316 KB	Output is correct
37	Correct	634 ms	26316 KB	Output is correct
38	Correct	2800 ms	26316 KB	Output is correct
39	Correct	2919 ms	26316 KB	Output is correct
40	Correct	3216 ms	26316 KB	Output is correct
41	Correct	3100 ms	26316 KB	Output is correct
42	Correct	3111 ms	26316 KB	Output is correct
43	Correct	957 ms	26316 KB	Output is correct
44	Correct	2036 ms	26596 KB	Output is correct
45	Correct	983 ms	26596 KB	Output is correct
46	Correct	2526 ms	31216 KB	Output is correct
47	Correct	61 ms	31216 KB	Output is correct
48	Correct	79 ms	31216 KB	Output is correct
49	Correct	564 ms	31216 KB	Output is correct
50	Correct	682 ms	31216 KB	Output is correct
51	Correct	1220 ms	32472 KB	Output is correct
52	Correct	1534 ms	36000 KB	Output is correct
53	Correct	1790 ms	38072 KB	Output is correct
54	Correct	1910 ms	42140 KB	Output is correct
55	Correct	1887 ms	44520 KB	Output is correct
56	Correct	2369 ms	48212 KB	Output is correct
57	Correct	2852 ms	51952 KB	Output is correct
58	Correct	2644 ms	54492 KB	Output is correct
59	Correct	2698 ms	58192 KB	Output is correct
60	Correct	2984 ms	60608 KB	Output is correct

답안 #66503

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