Submission #574355

#	Time	Username	Problem	Language	Result	Execution time	Memory
574355		wjajjsasqq	Fountain Parks (IOI21_parks)	C++17	5 / 100	375 ms	123904 KiB

parks

#include "parks.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

struct point {
	int x, y, ind;
};

struct bench {
	int x, y, dir;
};

bool operator<(point a, point b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool operator<(bench a, bench b) {
	if (a.x == b.x) {
		if (a.y == b.y) return a.dir < b.dir;
		return a.y < b.y;
	}
	return a.x < b.x;
}

bool operator==(bench a, bench b) {
	return !(a < b) && !(b < a);
}

const int N = 200005;
const int V = N * 4;
int n, e1[N * 2], e2[N * 2], ord[V], vis[V];
bool u[N];
std::vector<std::pair<int, int> > edg;
std::vector<int> g[V], t[V];
point a[N];
bench b1[N], b2[N];
std::vector<bench> ball;

int dx[] = {-1, 1, 0, 0}, dx1[] = {-1, 1, -1, 1};
int dy[] = {0, 0, -1, 1}, dy1[] = {-1, -1, 1, 1};

int locate(point p) {
	int pos = std::lower_bound(a, a + n, p) - a;
	if (pos < n && a[pos].x == p.x && a[pos].y == p.y) return pos;
	return -1;
}

void dfs(int ind) {
	u[ind] = 1;
	for (int i = 0; i < 4; ++i) {
		int next = locate({a[ind].x + dx[i] * 2, a[ind].y + dy[i] * 2});
		if (next != -1 && !u[next]) {
			edg.push_back(std::make_pair(ind, next));
			dfs(next);
		}
	}
}

void add_edge(int a, int b) {
	g[a].push_back(b);
	t[b].push_back(a);
	g[b ^ 1].push_back(a ^ 1);
	t[a ^ 1].push_back(b ^ 1);
}

void dfs0(int v) {
	static int dt = 0;
	vis[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) if (!vis[g[v][i]]) dfs0(g[v][i]);
	ord[dt++] = v;
}

int cmp;
void dfs1(int v) {
	vis[v] = cmp;
	for (int i = 0; i < (int)t[v].size(); ++i) if (!vis[t[v][i]]) dfs1(t[v][i]);
}

bool yes(int i) {
	return vis[i << 1 | 1] < vis[i << 1];
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	n = x.size();
	for (int i = 0; i < n; ++i) {
		a[i].x = x[i];
		a[i].y = y[i];
		a[i].ind = i;
	}
	std::sort(a, a + n);
	dfs(0);
	for (int i = 0; i < n; ++i) if (!u[i]) return 0;
	for (int i = 0; i < (int)edg.size(); ++i) {
		//printf("%d %d %d %d\n", a[edg[i].first].x, a[edg[i].first].y, a[edg[i].second].x, a[edg[i].second].y);
		if (a[edg[i].first].x == a[edg[i].second].x) {
			int mean = a[edg[i].first].y + a[edg[i].second].y >> 1;
			b1[i].x = a[edg[i].first].x - 1;
			b2[i].x = a[edg[i].first].x + 1;
			b1[i].y = b2[i].y = mean;
			b1[i].dir = 1;
			b2[i].dir = 3;
		} else {
			int mean = a[edg[i].first].x + a[edg[i].second].x >> 1;
			b1[i].x = b2[i].x = mean;
			b1[i].y = a[edg[i].first].y - 1;
			b2[i].y = a[edg[i].first].y + 1;
			b1[i].dir = 0;
			b2[i].dir = 2;
		}
		ball.push_back(b1[i]);
		ball.push_back(b2[i]);
	}
	std::sort(ball.begin(), ball.end());
	ball.resize(std::unique(ball.begin(), ball.end()) - ball.begin());
	for (int i = 0; i < (int)ball.size();) {
		int j = i;
		do {
			//printf("%d %d %d\n", ball[i].x, ball[i].y, ball[i].dir);
			++i;
		} while (i < (int)ball.size() && ball[i].x == ball[i - 1].x && ball[i].y == ball[i - 1].y);
		while (j < i) {
			for (int k = j + 1; k < i; ++k) add_edge(j << 1 | 1, k << 1);
			++j;
		}
	}
	for (int i = 0; i < (int)edg.size(); ++i) {
		e1[i] = std::lower_bound(ball.begin(), ball.end(), b1[i]) - ball.begin();
		e2[i] = std::lower_bound(ball.begin(), ball.end(), b2[i]) - ball.begin();
		add_edge(e1[i] << 1, e2[i] << 1 | 1);
	}
	for (int i = 0; i < ball.size() * 2; ++i) if (!vis[i]) dfs0(i);
	memset(vis, 0, sizeof vis);
	for (int i = (int)ball.size() * 2 - 1; i >= 0; --i) if (!vis[ord[i]]) {
		++cmp;
		dfs1(ord[i]);
	}
	for (int i = 0; i < (int)ball.size(); ++i) if (vis[i << 1] == vis[i << 1 | 1]) return 0;
	std::vector<int> ansu(edg.size()), ansv(edg.size()), ansa(edg.size()), ansb(edg.size());
	for (int i = 0; i < (int)edg.size(); ++i) {
		ansu[i] = a[edg[i].first].ind;
		ansv[i] = a[edg[i].second].ind;
		if (yes(e1[i])) {
			ansa[i] = ball[e1[i]].x;
			ansb[i] = ball[e1[i]].y;
		} else {
			ansa[i] = ball[e2[i]].x;
			ansb[i] = ball[e2[i]].y;
		}
	}
	build(ansu, ansv, ansa, ansb);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:98:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |    int mean = a[edg[i].first].y + a[edg[i].second].y >> 1;
      |               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:105:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |    int mean = a[edg[i].first].x + a[edg[i].second].x >> 1;
      |               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int i = 0; i < ball.size() * 2; ++i) if (!vis[i]) dfs0(i);
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30