oj.uz

답안 #66502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66502 2018-08-11T05:53:14 Z kingpig9 Collapse (JOI18_collapse) C++11
30 / 100
 3115 ms 25452 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) {
					//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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 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 11 ms 3344 KB Output is correct
5 Incorrect 22 ms 3480 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 8516 KB Output is correct
2 Correct 56 ms 8516 KB Output is correct
3 Incorrect 473 ms 14720 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 14720 KB Output is correct
2 Correct 65 ms 14720 KB Output is correct
3 Correct 91 ms 14720 KB Output is correct
4 Correct 140 ms 14720 KB Output is correct
5 Correct 644 ms 14720 KB Output is correct
6 Correct 661 ms 14720 KB Output is correct
7 Correct 1718 ms 20656 KB Output is correct
8 Correct 2591 ms 24964 KB Output is correct
9 Correct 79 ms 24964 KB Output is correct
10 Correct 633 ms 24964 KB Output is correct
11 Correct 2830 ms 25236 KB Output is correct
12 Correct 3112 ms 25308 KB Output is correct
13 Correct 3115 ms 25388 KB Output is correct
14 Correct 2905 ms 25388 KB Output is correct
15 Correct 3034 ms 25452 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 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 11 ms 3344 KB Output is correct
5 Incorrect 22 ms 3480 KB Output isn't correct
6 Halted 0 ms 0 KB -