oj.uz

답안 #756225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756225 2023-06-11T10:22:10 Z SanguineChameleon Flood (IOI07_flood) C++17
100 / 100
 128 ms 23448 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]++;
	}
	deque<int> q;
	for (int u = 1; u <= n; u++) {
		if (deg[u] == 1) {
			q.push_back(u);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (int d = 0; d < 4; d++) {
			int id = adj[u][d].first;
			int v = adj[u][d].second;
			if (id && deg[v]) {
				deg[v]--;
				if (deg[v] == 1) {
					q.push_back(v);
				}
				adj[u][d] = make_pair(0, 0);
				adj[v][d ^ 2] = make_pair(0, 0);
			}
		}
		deg[u] = 0;
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9732 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9736 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9832 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9784 KB Output is correct
2 Correct 7 ms 9744 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 11552 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 15952 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17396 KB Output is correct
2 Correct 117 ms 19980 KB Output is correct

Subtask #13
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 18708 KB Output is correct
2 Correct 128 ms 23448 KB Output is correct

Subtask #14
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 19784 KB Output is correct
2 Correct 64 ms 18344 KB Output is correct