Submission #961982

#	Time	Username	Problem	Language	Result	Execution time	Memory
961982		pedroslrey	Flood (IOI07_flood)	C++17	23 / 100	224 ms	39168 KiB

flood

#include <bits/stdc++.h>

using namespace std;

class union_find {
private:
	vector<int> rep, rnk;

public:
	union_find(int n) : rep (n), rnk (n) {
		for (int i = 0; i < n; ++i)
			rep[i] = i;
	}

	int find(int u) {
		if (rep[u] == u) return u;
		return rep[u] = find(rep[u]);
	}

	void une(int u, int v) {
		u = find(u); v = find(v);

		if (u == v) return;
		if (rnk[u] > rnk[v]) swap(u, v);
		else if (rnk[u] == rnk[v]) ++rnk[v];

		rep[u] = v;
	}
};

struct edge {
	pair<int, int> p1, p2;
	int u, v;
	int id;

	static int cnt;

	edge(pair<int, int> d1, pair<int, int> d2, int k) :
		p1 (d1), p2 (d2), u (cnt++), v (cnt++), id (k) { }

	int side(pair<int, int> p) { return p == p1 ? u : v; }
	int other_side(pair<int, int> p) { return p == p1 ? v : u; }

	bool operator<(edge other) {
		pair<int, int> p = (p1 == other.p1 || p1 == other.p2 ? p1 : p2);

		pair<int, int> tp = (p1 == p ? p2 : p1), op = (other.p1 == p ? other.p2 : other.p1);

		auto val = [p](pair<int, int> q) {
			if (q.first > p.first) return 1;
			if (q.second > p.second) return 2;
			if (q.first < p.first) return 3;
			return 4;
		};

		return val(tp) < val(op);
	}
};

int edge::cnt = 0;

vector<int> bfs(vector<vector<int>> &graph, vector<int> &start) {
	int n = graph.size();

	queue<int> q;
	vector<bool> marc(n);
	for (int s: start) {
		q.push(s);
		marc[s] = true;
	}

	vector<int> dist(n);

	while (!q.empty()) {
		int u = q.front(); q.pop();

		for (int v: graph[u])
			if (!marc[v]) {
				marc[v] = true;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
	}

	return dist;
}

int main() {
	int n;
	cin >> n;

	vector<pair<int, int>> coords(n);
	for (auto &[x, y]: coords)
		cin >> x >> y;

	int m;
	cin >> m;

	vector<vector<edge>> walls(n);
	vector<int> height(2*m);
	vector<edge> all_walls;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;

		--a; --b;

		edge e(coords[a], coords[b], i);

		height[e.u] = height[e.v] = e.p1.first;

		walls[a].push_back(e);
		walls[b].push_back(e);
		all_walls.push_back(e);
	}
	
	union_find regioes(2*m);
	for (int i = 0; i < n; ++i) {
		auto &viz = walls[i];
		auto p = coords[i];
		sort(viz.begin(), viz.end());

		for (int i = 0; i < viz.size(); ++i)
			regioes.une(viz[i].side(p), viz[(i + 1)%viz.size()].other_side(p));
	}

	vector<vector<int>> graph(2*m);
	union_find comps = regioes;
	for (auto &e: all_walls) {
		int ru = regioes.find(e.u), rv = regioes.find(e.v);
		if (ru != rv) {
			graph[ru].push_back(rv);
			graph[rv].push_back(ru);
			comps.une(ru, rv);
		}
	}

	vector<int> tallest(2*m);
	for (int i = 0; i < 2*m; ++i) {
		int c = comps.find(i);
		if (height[tallest[c]] < height[i])
			tallest[c] = regioes.find(i);
	}

	sort(tallest.begin(), tallest.end());
	tallest.erase(unique(tallest.begin(), tallest.end()), tallest.end());

	auto dist = bfs(graph, tallest);

	vector<int> ans;
	for (edge e: all_walls)
		if (dist[regioes.find(e.u)] == dist[regioes.find(e.v)])
			ans.push_back(e.id + 1);

	cout << ans.size() << "\n";
	for (int x: ans)
		cout << x << "\n";
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (int i = 0; i < viz.size(); ++i)
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9