oj.uz

답안 #66501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66501 2018-08-11T05:51:40 Z kingpig9 Collapse (JOI18_collapse) C++11
30 / 100
 3172 ms 25416 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++) {
				//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 <= q[1]; i++) {
				if (X[i] > pos) {
					int edgeid = E[i];
					if (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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3320 KB Output is correct
2 Correct 8 ms 3320 KB Output is correct
3 Correct 9 ms 3320 KB Output is correct
4 Correct 12 ms 3320 KB Output is correct
5 Incorrect 44 ms 3344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 8324 KB Output is correct
2 Correct 54 ms 8324 KB Output is correct
3 Incorrect 485 ms 14800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 14800 KB Output is correct
2 Correct 63 ms 14800 KB Output is correct
3 Correct 86 ms 14800 KB Output is correct
4 Correct 147 ms 14800 KB Output is correct
5 Correct 615 ms 14800 KB Output is correct
6 Correct 616 ms 14800 KB Output is correct
7 Correct 1412 ms 20680 KB Output is correct
8 Correct 2423 ms 24992 KB Output is correct
9 Correct 60 ms 24992 KB Output is correct
10 Correct 627 ms 24992 KB Output is correct
11 Correct 2662 ms 25416 KB Output is correct
12 Correct 2885 ms 25416 KB Output is correct
13 Correct 2889 ms 25416 KB Output is correct
14 Correct 3172 ms 25416 KB Output is correct
15 Correct 3079 ms 25416 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3320 KB Output is correct
2 Correct 8 ms 3320 KB Output is correct
3 Correct 9 ms 3320 KB Output is correct
4 Correct 12 ms 3320 KB Output is correct
5 Incorrect 44 ms 3344 KB Output isn't correct
6 Halted 0 ms 0 KB -