oj.uz

Submission #756118

# Submission time Handle Problem Language Result Execution time Memory
756118 2023-06-11T06:57:56 Z SanguineChameleon Flood (IOI07_flood) C++17
55 / 100
 52 ms 10852 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct point {
	int x, y, id;
};

bool cmp_x(point p1, point p2) {
	return p1.x < p2.x;
}

bool cmp_y(point p1, point p2) {
	return p1.y < p2.y;
}

bool cmp_id(point p1, point p2) {
	return p1.id < p2.id;
}

const int maxN = 1e5 + 20;
const int maxL = 1e3 + 20;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
point a[maxN];
bool dest[maxN * 2];
int wall[maxL][maxL][4];
bool done[maxL][maxL];

void just_do_it() {
	int N;
	cin >> N;
	a[0].x = -1;
	a[0].y = -1;
	a[0].id = 0;
	for (int i = 1; i <= N; i++) {
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
	}
	sort(a + 0, a + N + 1, cmp_x);
	int W = 0;
	for (int i = 0; i <= N; i++) {
		if (i < N && a[i].x != a[i + 1].x) {
			a[i].x = W++;
		}
		else {
			a[i].x = W;
		}
	}
	W++;
	sort(a + 0, a + N + 1, cmp_y);
	int L = 0;
	for (int i = 0; i <= N; i++) {
		if (i < N && a[i].y != a[i + 1].y) {
			a[i].y = L++;
		}
		else {
			a[i].y = L;
		}
	}
	L++;
	sort(a + 0, a + N + 1, cmp_id);
	int M;
	cin >> M;
	for (int i = 1; i <= M; i++) {
		int u, v;
		cin >> u >> v;
		if (a[u].x == a[v].x) {
			for (int j = min(a[u].y, a[v].y); j < max(a[u].y, a[v].y); j++) {
				wall[a[u].x - 1][j][0] = i;
				wall[a[u].x][j][1] = i;
			}
		}
		else {
			for (int j = min(a[u].x, a[v].x); j < max(a[u].x, a[v].x); j++) {
				wall[j][a[u].y - 1][2] = i;
				wall[j][a[u].y][3] = i;
			}
		}
	}
	deque<pair<int, int>> q;
	q.emplace_back(0, 0);
	while (!q.empty()) {
		vector<pair<pair<int, int>, int>> block;
		while (!q.empty()) {
			int cx = q.front().first;
			int cy = q.front().second;
			q.pop_front();
			if (done[cx][cy]) {
				continue;
			}
			for (int d = 0; d < 4; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (nx < 0 || nx >= W || ny < 0 || ny >= L) {
					continue;
				}
				if (wall[cx][cy][d]) {
					block.emplace_back(make_pair(cx, cy), d);
				}
				else {
					q.emplace_back(nx, ny);
				}
			}
			done[cx][cy] = true;
		}
		for (auto p: block) {
			int cx = p.first.first;
			int cy = p.first.second;
			int d = p.second;
			int nx = cx + dx[d];
			int ny = cy + dy[d];
			if (!done[nx][ny]) {
				dest[wall[cx][cy][d]] = true;
				q.emplace_back(nx, ny);
			}
		}
	}
	vector<int> res;
	for (int i = 1; i <= M; i++) {
		if (!dest[i]) {
			res.push_back(i);
		}
	}
	cout << res.size() << '\n';
	for (auto id: res) {
		cout << id << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2004 KB Output is correct
2 Correct 1 ms 852 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 2464 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 10852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 2712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 2936 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -