oj.uz

Submission #756227

# Submission time Handle Problem Language Result Execution time Memory
756227 2023-06-11T10:22:33 Z SanguineChameleon Flood (IOI07_flood) C++17
100 / 100
 104 ms 20296 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9700 KB Output is correct
2 Correct 5 ms 9732 KB Output is correct
3 Correct 7 ms 9636 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 7 ms 9752 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17216 KB Output is correct
2 Correct 104 ms 19792 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18504 KB Output is correct
2 Correct 96 ms 20296 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 19656 KB Output is correct
2 Correct 60 ms 16604 KB Output is correct