oj.uz

Submission #101781

# Submission time Handle Problem Language Result Execution time Memory
101781 2019-03-20T07:43:38 Z KCSC Collapse (JOI18_collapse) C++14
100 / 100
 3849 ms 27292 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]) {
			for (; ptx < all.size() and all[ptx].y <= qr.p; ++ptx) {
				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]
    for (; ptx < all.size() and all[ptx].y <= qr.p; ++ptx) {
           ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3072 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 9 ms 2976 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 12 ms 3072 KB Output is correct
6 Correct 24 ms 3816 KB Output is correct
7 Correct 7 ms 3044 KB Output is correct
8 Correct 8 ms 3072 KB Output is correct
9 Correct 13 ms 3328 KB Output is correct
10 Correct 24 ms 3456 KB Output is correct
11 Correct 38 ms 3968 KB Output is correct
12 Correct 28 ms 4044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8596 KB Output is correct
2 Correct 41 ms 8540 KB Output is correct
3 Correct 177 ms 11160 KB Output is correct
4 Correct 63 ms 9056 KB Output is correct
5 Correct 256 ms 12904 KB Output is correct
6 Correct 179 ms 8912 KB Output is correct
7 Correct 1862 ms 25444 KB Output is correct
8 Correct 307 ms 13548 KB Output is correct
9 Correct 44 ms 10072 KB Output is correct
10 Correct 49 ms 10200 KB Output is correct
11 Correct 190 ms 9464 KB Output is correct
12 Correct 390 ms 14696 KB Output is correct
13 Correct 1299 ms 19764 KB Output is correct
14 Correct 2769 ms 26916 KB Output is correct
15 Correct 2029 ms 26872 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8536 KB Output is correct
2 Correct 41 ms 8536 KB Output is correct
3 Correct 56 ms 8672 KB Output is correct
4 Correct 77 ms 8668 KB Output is correct
5 Correct 292 ms 8176 KB Output is correct
6 Correct 229 ms 8172 KB Output is correct
7 Correct 1376 ms 21432 KB Output is correct
8 Correct 2635 ms 25844 KB Output is correct
9 Correct 64 ms 10072 KB Output is correct
10 Correct 353 ms 9300 KB Output is correct
11 Correct 2823 ms 27064 KB Output is correct
12 Correct 3849 ms 27044 KB Output is correct
13 Correct 3137 ms 27032 KB Output is correct
14 Correct 3845 ms 27292 KB Output is correct
15 Correct 3010 ms 27160 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3072 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 9 ms 2976 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 12 ms 3072 KB Output is correct
6 Correct 24 ms 3816 KB Output is correct
7 Correct 7 ms 3044 KB Output is correct
8 Correct 8 ms 3072 KB Output is correct
9 Correct 13 ms 3328 KB Output is correct
10 Correct 24 ms 3456 KB Output is correct
11 Correct 38 ms 3968 KB Output is correct
12 Correct 28 ms 4044 KB Output is correct
13 Correct 41 ms 8596 KB Output is correct
14 Correct 41 ms 8540 KB Output is correct
15 Correct 177 ms 11160 KB Output is correct
16 Correct 63 ms 9056 KB Output is correct
17 Correct 256 ms 12904 KB Output is correct
18 Correct 179 ms 8912 KB Output is correct
19 Correct 1862 ms 25444 KB Output is correct
20 Correct 307 ms 13548 KB Output is correct
21 Correct 44 ms 10072 KB Output is correct
22 Correct 49 ms 10200 KB Output is correct
23 Correct 190 ms 9464 KB Output is correct
24 Correct 390 ms 14696 KB Output is correct
25 Correct 1299 ms 19764 KB Output is correct
26 Correct 2769 ms 26916 KB Output is correct
27 Correct 2029 ms 26872 KB Output is correct
28 Correct 34 ms 8536 KB Output is correct
29 Correct 41 ms 8536 KB Output is correct
30 Correct 56 ms 8672 KB Output is correct
31 Correct 77 ms 8668 KB Output is correct
32 Correct 292 ms 8176 KB Output is correct
33 Correct 229 ms 8172 KB Output is correct
34 Correct 1376 ms 21432 KB Output is correct
35 Correct 2635 ms 25844 KB Output is correct
36 Correct 64 ms 10072 KB Output is correct
37 Correct 353 ms 9300 KB Output is correct
38 Correct 2823 ms 27064 KB Output is correct
39 Correct 3849 ms 27044 KB Output is correct
40 Correct 3137 ms 27032 KB Output is correct
41 Correct 3845 ms 27292 KB Output is correct
42 Correct 3010 ms 27160 KB Output is correct
43 Correct 256 ms 13076 KB Output is correct
44 Correct 2173 ms 25268 KB Output is correct
45 Correct 314 ms 13600 KB Output is correct
46 Correct 2729 ms 25944 KB Output is correct
47 Correct 60 ms 10072 KB Output is correct
48 Correct 66 ms 10200 KB Output is correct
49 Correct 225 ms 9316 KB Output is correct
50 Correct 434 ms 11148 KB Output is correct
51 Correct 481 ms 14444 KB Output is correct
52 Correct 1172 ms 17248 KB Output is correct
53 Correct 1050 ms 17232 KB Output is correct
54 Correct 1987 ms 19816 KB Output is correct
55 Correct 1610 ms 19816 KB Output is correct
56 Correct 2126 ms 21964 KB Output is correct
57 Correct 2750 ms 25192 KB Output is correct
58 Correct 3444 ms 25256 KB Output is correct
59 Correct 2770 ms 27084 KB Output is correct
60 Correct 3595 ms 27120 KB Output is correct