Submission #756227

#	Time	Username	Problem	Language	Result	Execution time	Memory
756227		SanguineChameleon	Flood (IOI07_flood)	C++17	100 / 100	104 ms	20296 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 {
	long long x, y;
};
 
long long operator^(point p1, point p2) {
	return p1.x * p2.y - p1.y * p2.x;
}
 
const int maxn = 1e5 + 20;
point p[maxn];
pair<int, int> adj[maxn][4];
vector<int> adj_reg[maxn * 4];
int reg[maxn * 4];
pair<long long, int> area[maxn * 4];
int dist[maxn * 4];
int deg[maxn];
 
void just_do_it() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	int m;
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if (p[u].x == p[v].x) {
			if (p[u].y > p[v].y) {
				swap(u, v);
			}
			adj[u][0] = make_pair(i, v);
			adj[v][2] = make_pair(i + m, u);
		}
		else {
			if (p[u].x > p[v].x) {
				swap(u, v);
			}
			adj[u][1] = make_pair(i, v);
			adj[v][3] = make_pair(i + m, u);
		}
		deg[u]++;
		deg[v]++;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 4; j++) {
			if (adj[i][j].first && !reg[adj[i][j].first]) {
				cnt++;
				dist[cnt] = -1;
				area[cnt].second = cnt;
				int cur = adj[i][j].second;
				int dir = j;
				while (true) {
					dir = (dir + 1) % 4;
					while (!adj[cur][dir].first) {
						dir = (dir + 3) % 4;
					}
					reg[adj[cur][dir].first] = cnt;
					int nxt = adj[cur][dir].second;
					area[cnt].first += p[cur] ^ p[nxt];
					if (cur == i && nxt == adj[i][j].second) {
						break;
					}
					cur = nxt;
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		if (reg[i] != reg[i + m]) {
			adj_reg[reg[i]].push_back(reg[i + m]);
			adj_reg[reg[i + m]].push_back(reg[i]);
		}
	}
	sort(area + 1, area + cnt + 1, greater<>());
	for (int i = 1; i <= cnt; i++) {
		int u = area[i].second;
		if (dist[u] == -1) {
			dist[u] = 0;
			deque<int> q;
			q.push_back(u);
			while (!q.empty()) {
				u = q.front();
				q.pop_front();
				for (auto v: adj_reg[u]) {
					if (dist[v] == -1) {
						dist[v] = dist[u] + 1;
						q.push_back(v);
					}
				}
			}
		}
	}
	vector<int> res;
	for (int i = 1; i <= m; i++) {
		if (dist[reg[i]] == dist[reg[i + m]]) {
			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: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9