Submission #66569

#	Time	Username	Problem	Language	Result	Execution time	Memory
66569		aome	Flood (IOI07_flood)	C++17	100 / 100	166 ms	24880 KiB

flood

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, m;
int p[N];
int e[N][4];
int fr[N * 2], to[N * 2];
pair<int, int> a[N];
int visit[N * 2][2];

void add(int u, int v, int id) {
	if (a[u].first == a[v].first) {
		if (a[u].second < a[v].second) e[u][1] = id; else e[u][3] = id;
	}
	else {
		if (a[u].first < a[v].first) e[u][2] = id; else e[u][0] = id;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		p[i] = i;
		cin >> a[i].first >> a[i].second;
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> fr[i] >> to[i];
		add(fr[i], to[i], i), add(to[i], fr[i], i);
	}
	sort(p + 1, p + 1 + n, [&] (int x, int y) {
		return a[x] < a[y];
	});
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		while (1) {
			bool found = 0;
			int u = p[i], d = 2;
			for (int j = 0; j < 4; ++j) {
				int id = e[u][j];
				found |= id && !visit[id][j < 2];
			}
			if (!found) break;
			++cnt;
			vector<int> buffer;
			while (1) {
				for (int j = 0; j < 4; ++j) {
					int k = (d + j + 3) % 4; 
					int id = e[u][k];
					if (id && !visit[id][k < 2]) {
						u = fr[id] + to[id] - u, d = k, visit[id][k < 2] = cnt, buffer.push_back(id); break;
					}
				}
				if (u == p[i]) break;
			}
			for (auto id : buffer) {
				if (!visit[id][0]) visit[id][0] = -1;
				if (!visit[id][1]) visit[id][1] = -1;
			}
		}
	}
	cnt = 0;
	for (int i = 1; i <= m; ++i) {
		if (visit[i][0] == visit[i][1]) cnt++;
	}
	cout << cnt << '\n';
	for (int i = 1; i <= m; ++i) {
		if (visit[i][0] == visit[i][1]) cout << i << '\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: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9