oj.uz

Submission #226014

# Submission time Handle Problem Language Result Execution time Memory
226014 2020-04-22T10:32:03 Z Minnakhmetov Sweeping (JOI20_sweeping) C++14
100 / 100
 5262 ms 514920 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 2e6 + 5;

struct Q {
	int t, x, y, z;
};

struct DSU {
	int val[N], a[N];
	vector<int> v[N];

	int find_set(int x) {
		return a[x] < 0 ? x : a[x];
	}

	int get_val(int x) {
		return val[find_set(x)];
	}

	void reset(int x, int y) {
		a[x] = -1;
		val[x] = y;
		v[x] = {x};
	}

	void mrg(int x, int y) {
		x = find_set(x);
		y = find_set(y);
		if (x == y)
			return;
		if (v[x].size() < v[y].size()) {
			swap(x, y);
		}
		for (const int &el : v[y]) {
			v[x].push_back(el);
			a[el] = x;
		}
		v[y].clear();
	}

	void set_val(int x, int y) {
		x = find_set(x);
		val[x] = y;
	}

} dsu_x, dsu_y;

pair<int, int> ans[N];
bool send_to_up[N], send_to_right[N];
vector<int> selected;

void get_not_gr_than_x(priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> &pq, int x) {
	selected.clear();
	while (!pq.empty() && pq.top().first <= x) {
		selected.push_back(pq.top().second);
		pq.pop();
	}
}

void upd_pq(priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> &pq, DSU &dsu, int x) {

	get_not_gr_than_x(pq, x);

	if (!selected.empty()) {
		for (const int &y : selected) {
			dsu.mrg(y, selected[0]);
		}
		dsu.set_val(selected[0], x);
		pq.push({x, dsu.find_set(selected[0])});
	}
}

priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> pq_x, pq_y;

void solve(int offset_x, int offset_y, int n, vector<Q> qrs) {
	if (qrs.empty())
		return;

	while (!pq_x.empty())
		pq_x.pop();

	while (!pq_y.empty())
		pq_y.pop();

	// cout << n << " " << offset_x << " " << offset_y << "\n";
	// for (Q q : qrs) {
	// 	cout << q.t << " " << q.x << " " << q.y << " " << q.z << "\n";
	// }
	// cout << "\n";

	vector<Q> up_qrs, rt_qrs;

	int sq_side = (n + 1) / 2;

	for (const Q &c : qrs) {
		if (c.t == 1) {
			if (send_to_up[c.x]) {
				up_qrs.push_back(c);
			}
			else if (send_to_right[c.x]) {
				rt_qrs.push_back(c);
			}
			else {
				ans[c.y] = {dsu_x.get_val(c.x) + offset_x, 
					dsu_y.get_val(c.x) + offset_y};
			}
		}
		else if (c.t == 2) {
			if (c.x < sq_side) {
				rt_qrs.push_back(c);
				get_not_gr_than_x(pq_y, c.x);

				for (const int &gr : selected) {
					for (const int &el : dsu_y.v[gr]) {
						if (!send_to_right[el] && !send_to_up[el]) {
							Q new_q;
							new_q.t = 4;
							new_q.x = n - c.x - sq_side;
							new_q.y = dsu_y.get_val(el);
							send_to_right[el] = true;
							new_q.z = el;
							rt_qrs.push_back(new_q);
						}
					}
				}
			}
			else {
				upd_pq(pq_x, dsu_x, n - c.x);
				up_qrs.push_back(c);
				up_qrs.back().x = c.x - sq_side;
			}
		}
		else if (c.t == 3) {
			if (c.x < sq_side) {
				up_qrs.push_back(c);
				get_not_gr_than_x(pq_x, c.x);

				for (const int &gr : selected) {
					for (const int &el : dsu_x.v[gr]) {
						if (!send_to_right[el] && !send_to_up[el]) {
							Q new_q;
							new_q.t = 4;
							new_q.x = dsu_x.get_val(el);
							new_q.y = n - c.x - sq_side;
							send_to_up[el] = true;
							new_q.z = el;
							up_qrs.push_back(new_q);
						}
					}
				}
			}
			else {
				upd_pq(pq_y, dsu_y, n - c.x);
				rt_qrs.push_back(c);
				rt_qrs.back().x = c.x - sq_side;
			}
		}
		else {
			send_to_up[c.z] = false;
			send_to_right[c.z] = false;
			
			if (c.x > sq_side) {
				rt_qrs.push_back(c);
				rt_qrs.back().x -= sq_side;
				send_to_right[c.z] = true;
			}
			else if (c.y > sq_side) {
				up_qrs.push_back(c);
				up_qrs.back().y -= sq_side;
				send_to_up[c.z] = true;
			}
			else {
				dsu_x.reset(c.z, c.x);
				dsu_y.reset(c.z, c.y);
				pq_x.push({c.x, c.z});
				pq_y.push({c.y, c.z});
			}
		}
	}

	if (n != 0) {
		solve(offset_x, offset_y + sq_side, n - sq_side, up_qrs);
		solve(offset_x + sq_side, offset_y, n - sq_side, rt_qrs);
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q, z = 0;
    cin >> n >> m >> q;

    vector<Q> qrs;

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	qrs.push_back({4, x, y, z++});
    }

    int ask_qr_ct = 0;

    for (int i = 0; i < q; i++) {
    	Q new_q;
    	cin >> new_q.t >> new_q.x;

    	if (new_q.t == 1) {
    		new_q.x--;
    		new_q.y = ask_qr_ct++;
    	}
    	else if (new_q.t == 4) {
    		cin >> new_q.y;
    		new_q.z = z++;
    	}

    	qrs.push_back(new_q);
    }

    solve(0, 0, n, qrs);

    for (int i = 0; i < ask_qr_ct; i++) {
    	cout << ans[i].first << " " << ans[i].second << "\n";
    }

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 95480 KB Output is correct
2 Correct 64 ms 94968 KB Output is correct
3 Correct 59 ms 95224 KB Output is correct
4 Correct 67 ms 95440 KB Output is correct
5 Correct 64 ms 95448 KB Output is correct
6 Correct 59 ms 95096 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3461 ms 286600 KB Output is correct
2 Correct 3369 ms 308768 KB Output is correct
3 Correct 3404 ms 300388 KB Output is correct
4 Correct 2719 ms 368760 KB Output is correct
5 Correct 5262 ms 317208 KB Output is correct
6 Correct 4293 ms 344600 KB Output is correct
7 Correct 3443 ms 306516 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2680 ms 305564 KB Output is correct
2 Correct 2665 ms 328216 KB Output is correct
3 Correct 2138 ms 357976 KB Output is correct
4 Correct 2920 ms 441868 KB Output is correct
5 Correct 2775 ms 388380 KB Output is correct
6 Correct 2537 ms 325916 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2680 ms 305564 KB Output is correct
2 Correct 2665 ms 328216 KB Output is correct
3 Correct 2138 ms 357976 KB Output is correct
4 Correct 2920 ms 441868 KB Output is correct
5 Correct 2775 ms 388380 KB Output is correct
6 Correct 2537 ms 325916 KB Output is correct
7 Correct 3293 ms 308424 KB Output is correct
8 Correct 3418 ms 298656 KB Output is correct
9 Correct 3340 ms 305180 KB Output is correct
10 Correct 2741 ms 340752 KB Output is correct
11 Correct 3817 ms 398472 KB Output is correct
12 Correct 4361 ms 356888 KB Output is correct
13 Correct 3906 ms 493148 KB Output is correct
14 Correct 249 ms 170176 KB Output is correct
15 Correct 942 ms 236504 KB Output is correct
16 Correct 3210 ms 304408 KB Output is correct
17 Correct 3223 ms 302264 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 95480 KB Output is correct
2 Correct 64 ms 94968 KB Output is correct
3 Correct 59 ms 95224 KB Output is correct
4 Correct 67 ms 95440 KB Output is correct
5 Correct 64 ms 95448 KB Output is correct
6 Correct 59 ms 95096 KB Output is correct
7 Correct 3461 ms 286600 KB Output is correct
8 Correct 3369 ms 308768 KB Output is correct
9 Correct 3404 ms 300388 KB Output is correct
10 Correct 2719 ms 368760 KB Output is correct
11 Correct 5262 ms 317208 KB Output is correct
12 Correct 4293 ms 344600 KB Output is correct
13 Correct 3443 ms 306516 KB Output is correct
14 Correct 2680 ms 305564 KB Output is correct
15 Correct 2665 ms 328216 KB Output is correct
16 Correct 2138 ms 357976 KB Output is correct
17 Correct 2920 ms 441868 KB Output is correct
18 Correct 2775 ms 388380 KB Output is correct
19 Correct 2537 ms 325916 KB Output is correct
20 Correct 3293 ms 308424 KB Output is correct
21 Correct 3418 ms 298656 KB Output is correct
22 Correct 3340 ms 305180 KB Output is correct
23 Correct 2741 ms 340752 KB Output is correct
24 Correct 3817 ms 398472 KB Output is correct
25 Correct 4361 ms 356888 KB Output is correct
26 Correct 3906 ms 493148 KB Output is correct
27 Correct 249 ms 170176 KB Output is correct
28 Correct 942 ms 236504 KB Output is correct
29 Correct 3210 ms 304408 KB Output is correct
30 Correct 3223 ms 302264 KB Output is correct
31 Correct 3208 ms 338480 KB Output is correct
32 Correct 3373 ms 300616 KB Output is correct
33 Correct 3295 ms 291396 KB Output is correct
34 Correct 3740 ms 327060 KB Output is correct
35 Correct 3793 ms 326904 KB Output is correct
36 Correct 2705 ms 349136 KB Output is correct
37 Correct 4747 ms 474832 KB Output is correct
38 Correct 4056 ms 514920 KB Output is correct
39 Correct 3743 ms 456112 KB Output is correct
40 Correct 3220 ms 318744 KB Output is correct