oj.uz

Submission #756185

# Submission time Handle Problem Language Result Execution time Memory
756185 2023-06-11T09:30:18 Z SanguineChameleon Flood (IOI07_flood) C++17
23 / 100
 105 ms 37668 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];

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);
		}
	}
	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) {
						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) {
			assert(area[i].first > 0);
			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 6 ms 9684 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9704 KB Output is correct
2 Correct 5 ms 9716 KB Output is correct
3 Runtime error 15 ms 19540 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 19556 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 19540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

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

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 19668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 19668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 19668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 22608 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 30916 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 34124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 35460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 37668 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -