Submission #756118

#	Time	Username	Problem	Language	Result	Execution time	Memory
756118		SanguineChameleon	Flood (IOI07_flood)	C++17	55 / 100	52 ms	10852 KiB

flood

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9