oj.uz

Submission #961993

# Submission time Handle Problem Language Result Execution time Memory
961993 2024-04-13T02:04:27 Z pedroslrey Flood (IOI07_flood) C++17
100 / 100
 224 ms 30496 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>

using namespace std;

class union_find {
private:
	vector<int> rep;

public:
	union_find(int n) : rep (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;

		rep[u] = v;
	}
};

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

	static int cnt;

	edge() { }
	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) if (s < n) {
		q.push(s);
		marc[s] = true;

		// cerr << "starting on " << s << "\n";
	}

	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 + 1);
	vector<edge> all_walls(m);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;

		--a; --b;

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


		walls[a].push_back(e);
		walls[b].push_back(e);
		all_walls[i] = e;

		if (e.p1.second == e.p2.second) 
			height[e.side(min(e.p1, e.p2))] = e.p1.second;
	}

	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));
	}

	walls.clear();

	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);

			// cerr << ru << " " << rv << "\n";
		}
	}

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

	for (int &x: tallest) if (x != 2*m) {
		// cerr << x << " TALLEST OF " << comps.find(x) << " " << height[x] << "\n";
		x = regioes.find(x);
	}

	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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 14924 KB Output is correct
2 Correct 199 ms 28040 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 25368 KB Output is correct
2 Correct 224 ms 30496 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 30316 KB Output is correct
2 Correct 127 ms 22284 KB Output is correct