【求助】本地能过,洛谷上无原因CE是为什么(P4646)
  • 板块灌水区
  • 楼主QIANKUNXIAO
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/12/12 22:29
  • 上次更新2023/11/3 22:19:01
查看原帖
【求助】本地能过,洛谷上无原因CE是为什么(P4646)
31437
QIANKUNXIAO楼主2021/12/12 22:29

如题,萌新一枚,用对偶图做P4646,代码如下

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, w, a_cnt;
int depth[100005] = {0}, nbrs[100005] = {0}; //"a_cnt" is count of areas
int ans[100005], k = 0;
vector<int> nbr[100005]; //"nbr" represents neighbor
bool vis[100005] = {0};

struct point_ {
	int x = -1, y = -1;
	int walls[4] = {0};
} point[100005];

struct wall_ {
	int start = 0, end = 0, area = 0;
	short dir = -1;
} wall[400005];

queue<int> q;

void input () {
	cin >> n;
	for (int i=1; i<=n; ++i)
		cin >> point[i].x >> point[i].y;
	cin >> w;
	for (int i=1; i<=w; ++i) {
		cin >> wall[i].start >> wall[i].end;
		wall[w+i].start = wall[i].end;
		wall[w+i].end = wall[i].start;
	}
	for (int i=1; i<=2*w; ++i) {
		if (point[wall[i].start].x == point[wall[i].end].x)
			wall[i].dir = 2 * (point[wall[i].start].y > point[wall[i].end].y);
		if (point[wall[i].start].y == point[wall[i].end].y)
			wall[i].dir = 2 * (point[wall[i].start].x < point[wall[i].end].x) + 1;	
		point[wall[i].start].walls[wall[i].dir] = i;
	}
	return;
}

int find_area () {
	for (int i=1; i<=2*w; ++i) {
		if (wall[i].area) continue;
		wall[i].area = ++a_cnt;
		int now_ = i;
		while (true) {
			int next_ = 0, reverse_dir;
			for (int j=1; j<=4; ++j) {
				if (next_) continue;			
				reverse_dir = wall[now_].dir>=2 ? (wall[now_].dir-2) : (wall[now_].dir+2);
				next_ = point[wall[now_].end].walls[(j+reverse_dir)%4];
			}
			now_ = next_;
			if (now_ == i) break;
			wall[now_].area = a_cnt;
		}
	}
	int min_y = 2147483647, min_yx = 2147483647, min_p;
	for (int i=1; i<=n; ++i)
		if (point[i].y <= min_y) {
			if (point[i].y < min_y)
					min_yx = 2147483647;
			min_y = point[i].y;
			if (point[i].x <= min_yx) {
				min_yx = point[i].x;
				min_p = i;
			}
		}
	return min_p;
}

void build () {
	for (int i=1; i<=w; ++i)
		if (wall[i].area != wall[i+w].area) {
			nbr[wall[i].area].push_back (wall[i+w].area);
			nbrs[wall[i].area]++;
		}
	return;
}

void bfs () {
	int start_area = find_area ();
	build ();
	q.push (start_area);
	vis[start_area] = 1;
	while (!q.empty ()) {
		int now_area = q.front ();
		q.pop ();
		for (int i=1; i<=nbrs[now_area]; ++i)
			if (!vis[nbr[now_area][i]]) {
				vis[nbr[now_area][i]] = 1;
				q.push (nbr[now_area][i]);
				depth[nbr[now_area][i]] = depth[now_area] + 1;
			}
	}
	return;
}

void print () {
	for (int i=1; i<=w; ++i)
		if (depth[wall[i].area] == depth[wall[i+w].area])
			ans[++k] = i;
	cout << k << endl;
	for (int i=1; i<=k; ++i)
		cout << ans[i] << endl;
	return;
}

int main () {
	ios::sync_with_stdio (false);
	cin.tie (0);
	input ();
	bfs ();
	print ();
	return 0;
}

代码交上去之后显示CE“编译错误”但不显示错误原因 求助

2021/12/12 22:29
加载中...