oj.uz

Submission #59393

# Submission time Handle Problem Language Result Execution time Memory
59393 2018-07-22T00:36:33 Z kingpig9 Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 19248 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;

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

struct union_find {
	int par[100010];  //don't forget to init
	int ncomp;

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	bool merge (int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return false;
		}
		par[x] = y;
		ncomp--;
		return true;
	}

	void reset (int sz) {
		for (int i = 0; i < sz; i++) {
			par[i] = i;
		}
		ncomp = sz;
	}
};

namespace subtask1 {
	const int MAXN = 5010;

	map<pii, int> mpind;
	bitset<MAXN> active[MAXN];
	union_find uf;

	vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
		for (int i = 0; i < C; i++) {
			if (i) {
				active[i] = active[i - 1];
			}

			int indxy;
			if (mpind.count(pii(X[i], Y[i]))) {
				indxy = mpind[pii(X[i], Y[i])];
			} else {
				indxy = mpind[pii(X[i], Y[i])] = i;
			}

			if (T[i] == 0) {
				active[i][indxy] = true;
			} else {
				active[i][indxy] = false;
			}
		}

		vector<int> ans;
		for (int i = 0; i < Q; i++) {
			uf.reset(N);
			//day W[i]
			for (int j = 0; j < C; j++) {
				if (active[W[i]][j]) {
					if (!(X[j] <= P[i] && P[i] + 1 <= Y[j])) {
						uf.merge(X[j], Y[j]);
						debug("avail %d %d\n", X[j], Y[j]);
					}
				}
			}

			debug("warm\n");
			ans.push_back(uf.ncomp);
		}

		return ans;
	}
}

//should have gotten this...too bad not enough time.
namespace subtask2 {
	const int MAXN = 1 << 17;

	struct union_findr {
		int par[MAXN], sz[MAXN];    //don't forget to init
		int ncmp;
		stack<pair<int*, int>> stk;

		void init (int n) {
			ncmp = n;
			for (int i = 0; i < n; i++) {
				par[i] = i;
				sz[i] = 1;
			}
		}

		int find (int x) {
			return x == par[x] ? x : find(par[x]);
		}

		void change (int &x, int y) {
			stk.push(make_pair(&x, x));
			x = y;
		}

		void merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return;
			}
			if (sz[x] > sz[y]) {
				swap(x, y);
			}
			change(sz[y], sz[y] + sz[x]);
			change(par[x], y);
			change(ncmp, ncmp - 1);
		}

		void rollback (int s) {
			while (stk.size() > s) {
				pair<int*, int> p = stk.top();
				stk.pop();
				*(p.fi) = p.se;
			}
		}
	};

	union_findr ufl, ufr;
	vector<pii> tree[2 * MAXN];

	void update (int a, int b, pii v, int cur = 1, int lt = 0, int rt = MAXN) {
		if (rt <= a || b <= lt) {
			return;
		}

		if (a <= lt && rt <= b) {
			tree[cur].push_back(v);
			return;
		}

		int mid = (lt + rt) / 2;
		update(a, b, v, 2 * cur, lt, mid);
		update(a, b, v, 2 * cur + 1, mid, rt);
	}

	int P;
	int ncompt[MAXN];	//number of components at this time

	void dfs (int cur = 1, int lt = 0, int rt = MAXN) {
		if (lt >= C) {
			return;
		}

		int statel = ufl.stk.size(), stater = ufr.stk.size();

		//add edges
		for (pii e : tree[cur]) {
			if (e.se <= P) {
				ufl.merge(e.fi, e.se);
			} else if (e.fi > P) {
				ufr.merge(e.fi, e.se);
			}
		}

		if (rt - lt == 1) {
			ncompt[lt] = ufl.ncmp + ufr.ncmp - N;	//minus N -- we both initted to N.
		} else {
			int mid = (lt + rt) / 2;
			dfs(2 * cur, lt, mid);
			dfs(2 * cur + 1, mid, rt);
		}

		ufl.rollback(statel);
		ufr.rollback(stater);
	}

	vector<int> go (vector<int> T, vector<int> X, vector<int> Y, vector<int> W, int ppppp) {
		ufl.init(N);
		ufr.init(N);
		P = ppppp;
		map<pii, int> mp;

		for (int i = 0; i < C; i++) {
			pii e(X[i], Y[i]);
			if (mp.count(e)) {
				update(mp.at(e), i, e);
				mp.erase(e);
			} else {
				mp[e] = i;
			}
		}

		for (auto it : mp) {
			update(it.se, C, it.fi);
		}

		//ok let's go!
		dfs();

		vector<int> ans;
		for (int day : W) {
			ans.push_back(ncompt[day]);
		}
		return ans;
	}
}

namespace subtask3 {
	//6s, 512MB

	struct query {
		int day, pos;	//which day? which position?
		int id;	//what is the index?
	};

	bool operator < (query q1, query q2) {
		return q1.day < q2.day;
	}

	const int MAXN = 1e5 + 320;
	const int SQRT = 320;
	union_find uf[SQRT];
	int qid[SQRT];
	vector<pii> edges;
	vector<query> qu;
	int ans[MAXN];

	vector<int> go (vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
		for (int i = 0; i < Q; i++) {
			qu.push_back((query) {W[i], P[i], i});
		}
		sort(all(qu));

		for (int i = 0; i < Q; i += SQRT) {
			//i to i + Q.
			int nq = 0;
			for (int j = i; j < Q && j < i + SQRT; j++) {
				//let's add this query in
				uf[j - i].reset(N);
				nq++;
			}

			//construction plan in this day
			int cday = 0;
			for (int j = i; j < Q && j < i + SQRT; j++) {
				int day = qu[j].day;
				for (; cday <= day; cday++) {
					//let's add this day in to ALL of 'em
					for (int k = 0; k < nq; k++) {
						if (!(X[cday] <= qu[j].pos && qu[j].pos + 1 <= Y[cday])) {
							uf[k].merge(X[cday], Y[cday]);
						}
					}
				}

				//ok let's now query this one!
				ans[qu[j].id] = uf[j - i].ncomp;
			}
		}
		return vector<int> (ans, ans + Q);
	}
}

vector<int> simulateCollapse (int n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	N = n;
	C = X.size();
	Q = W.size();

	for (int i = 0; i < C; i++) {
		if (X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
	}

	if (N <= 5000 && Q <= 5000) {
		return subtask1::go(T, X, Y, W, P);
	} else if (count(all(T), 0) == T.size()) {
		return subtask3::go(X, Y, W, P);
	} else if ((set<int> (all(P))).size() == 1) {
		return subtask2::go(T, X, Y, W, P[0]);
	}
}

Compilation message

collapse.cpp: In member function 'void subtask2::union_findr::rollback(int)':
collapse.cpp:134:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (stk.size() > s) {
           ~~~~~~~~~~~^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:291:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  } else if (count(all(T), 0) == T.size()) {
             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
collapse.cpp:296:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9976 KB Output is correct
2 Correct 10 ms 9976 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 12 ms 9976 KB Output is correct
5 Correct 78 ms 10080 KB Output is correct
6 Correct 199 ms 10436 KB Output is correct
7 Correct 23 ms 10436 KB Output is correct
8 Correct 25 ms 10436 KB Output is correct
9 Correct 82 ms 10436 KB Output is correct
10 Correct 211 ms 10580 KB Output is correct
11 Correct 263 ms 10660 KB Output is correct
12 Correct 371 ms 10660 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 12644 KB Output is correct
2 Correct 37 ms 12644 KB Output is correct
3 Correct 155 ms 17960 KB Output is correct
4 Correct 76 ms 17960 KB Output is correct
5 Correct 203 ms 19248 KB Output is correct
6 Correct 1967 ms 19248 KB Output is correct
7 Execution timed out 15056 ms 19248 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19248 KB Output is correct
2 Incorrect 51 ms 19248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9976 KB Output is correct
2 Correct 10 ms 9976 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 12 ms 9976 KB Output is correct
5 Correct 78 ms 10080 KB Output is correct
6 Correct 199 ms 10436 KB Output is correct
7 Correct 23 ms 10436 KB Output is correct
8 Correct 25 ms 10436 KB Output is correct
9 Correct 82 ms 10436 KB Output is correct
10 Correct 211 ms 10580 KB Output is correct
11 Correct 263 ms 10660 KB Output is correct
12 Correct 371 ms 10660 KB Output is correct
13 Correct 42 ms 12644 KB Output is correct
14 Correct 37 ms 12644 KB Output is correct
15 Correct 155 ms 17960 KB Output is correct
16 Correct 76 ms 17960 KB Output is correct
17 Correct 203 ms 19248 KB Output is correct
18 Correct 1967 ms 19248 KB Output is correct
19 Execution timed out 15056 ms 19248 KB Time limit exceeded
20 Halted 0 ms 0 KB -