oj.uz

Submission #101780

# Submission time Handle Problem Language Result Execution time Memory
101780 2019-03-20T07:39:31 Z KCSC Collapse (JOI18_collapse) C++14
0 / 100
 15000 ms 12392 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;
const int SIZE = 305;

struct Edge {
	int x, y, t1, t2;
	
	Edge(int _x, int _y, int _t1, int _t2) :
		x(_x), y(_y), t1(_t1), t2(_t2) {}

	bool operator <(const Edge &other) const {
		return (*this).y < other.y; }
};

struct Query {
	int p, t, id;

	Query(int _p, int _t, int _id) :
		p(_p), t(_t), id(_id) {}

	bool operator <(const Query &other) const {
		return (*this).p < other.p; }
};

struct UndoDSU {
	int cnt, siz;
	int fth[DIM], lst[DIM], szt[DIM];

	UndoDSU(int _siz = DIM - 1) : 
		cnt(0), siz(_siz) {}

	inline void initialize(void) {
		cnt = 0;
		for (int i = 1; i <= siz; ++i) {
			fth[i] = i; szt[i] = 1; } }

	inline int getRoot(int x) {
		while (fth[x] != x) {
			x = fth[x]; }
		return x; }

	bool unite(int x, int y) {
		x = getRoot(x); y = getRoot(y);
		if (szt[x] < szt[y]) {
			swap(x, y); }
		if (x != y) {
			lst[++cnt] = y; szt[x] += szt[y]; fth[y] = x;
			return true; }
		else {
			return false; } }

	void undo(int nr) {
		assert(nr <= cnt);
		for (; cnt > nr; --cnt) {
			int y = lst[cnt], x = fth[y];
			szt[x] -= szt[y]; fth[y] = y; } }
};

void solve(int n, int m, int t, int k, 
	vector<Edge> &edg, vector<Query> &qry, vector<int> &ans) {
	
	UndoDSU dsu(n); vector<Query> lst[DIM]; vector<Edge> all, psb;

	for (auto it : qry) {
		lst[it.t / SIZE * SIZE].push_back(it); }
	for (int i = 0; i <= m; i += SIZE) {
		dsu.initialize(); all.clear(); psb.clear();
		for (auto it : edg) {
			if (it.t1 <= i and it.t2 >= i + SIZE - 1) {
				all.push_back(it); }
			else if (it.t2 >= i and it.t1 <= i + SIZE - 1) {
				psb.push_back(it); } }
		sort(all.begin(), all.end()); 
		sort(lst[i].begin(), lst[i].end());
		int ptx = 0;
		for (auto qr : lst[i]) {
			while (ptx < all.size() and all[ptx].y <= qr.p) {
				dsu.unite(all[ptx].x, all[ptx].y); }
			int cnt = dsu.cnt;
			for (auto it : psb) {
				if (it.y <= qr.p and it.t1 <= qr.t and qr.t <= it.t2) {
					dsu.unite(it.x, it.y); } }
			ans[qr.id] -= dsu.cnt; dsu.undo(cnt); } } }
	

vector<int> simulateCollapse(int n, 
	vector<int> _typ, vector<int> _crd1, vector<int> _crd2,
	vector<int> _tim, vector<int> _plc) {

	const int m = (int) _typ.size(), k = (int) _tim.size();
	vector<int> ans(k, n); vector<Edge> edg; vector<Query> qry;
	map<pair<int, int>, int> mmp;

	for (int i = 1; i <= m; ++i) {
		int x =_crd1[i - 1], y = _crd2[i - 1];
		if (++x > ++y) {
			swap(x, y); }
		if (_typ[i - 1] == 0) {
			mmp[make_pair(x, y)] = i; }
		else {
			edg.push_back(Edge(x, y, mmp[make_pair(x, y)], i - 1)); 
			mmp.erase(mmp.find(make_pair(x, y))); } }
	for (auto it : mmp) {
		int x, y; tie(x, y) = it.first;
		edg.push_back(Edge(x, y, it.second, m)); } 
	for (int i = 1; i <= k; ++i) {
		int p = _plc[i - 1] + 1, t = _tim[i - 1] + 1;
		qry.push_back(Query(p, t, i - 1)); }
	solve(n, m, edg.size(), k, edg, qry, ans);
	for (auto &it : edg) {
		it.x = n - it.x + 1, it.y = n - it.y + 1;
		swap(it.x, it.y); }
	for (auto &it : qry) {
		it.p = n - it.p; }
	solve(n, m, edg.size(), k, edg, qry, ans);
	return ans; }

#ifdef HOME
int main(void) {
	freopen("collapse.in", "r", stdin);
	freopen("collapse.out", "w", stdout);
	int n, c, q; cin >> n >> c >> q;
	vector<int> t(c, 0), x(c, 0), y(c, 0), w(q, 0), p(q, 0);
	for (int i = 0; i < c; ++i) {
		cin >> t[i] >> x[i] >> y[i]; }
	for (int i = 0; i < q; ++i) {
		cin >> w[i] >> p[i]; }
	vector<int> ans = simulateCollapse(n, t, x, y, w, p);
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\n"; }
	return 0; }
#endif

Compilation message

collapse.cpp: In function 'void solve(int, int, int, int, std::vector<Edge>&, std::vector<Query>&, std::vector<int>&)':
collapse.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ptx < all.size() and all[ptx].y <= qr.p) {
           ~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3200 KB Output is correct
2 Correct 6 ms 2984 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 2980 KB Output is correct
5 Correct 12 ms 3200 KB Output is correct
6 Execution timed out 15013 ms 3584 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8920 KB Output is correct
2 Correct 47 ms 8892 KB Output is correct
3 Execution timed out 15057 ms 12392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8920 KB Output is correct
2 Correct 69 ms 8916 KB Output is correct
3 Correct 66 ms 9048 KB Output is correct
4 Correct 83 ms 9056 KB Output is correct
5 Correct 330 ms 8888 KB Output is correct
6 Execution timed out 15034 ms 8812 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3200 KB Output is correct
2 Correct 6 ms 2984 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 2980 KB Output is correct
5 Correct 12 ms 3200 KB Output is correct
6 Execution timed out 15013 ms 3584 KB Time limit exceeded
7 Halted 0 ms 0 KB -