oj.uz

Submission #574355

# Submission time Handle Problem Language Result Execution time Memory
574355 2022-06-08T11:36:32 Z wjajjsasqq Fountain Parks (IOI21_parks) C++17
5 / 100
 375 ms 123904 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct
17 Incorrect 19 ms 40916 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct
17 Incorrect 19 ms 40916 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct
17 Correct 22 ms 40932 KB Output is correct
18 Incorrect 20 ms 41032 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct
17 Incorrect 375 ms 123904 KB Tree @(100001, 100001) appears more than once: for edges on positions 99999 and 100000
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40916 KB Output is correct
2 Correct 22 ms 40968 KB Output is correct
3 Correct 20 ms 37880 KB Output is correct
4 Correct 23 ms 40932 KB Output is correct
5 Correct 19 ms 40948 KB Output is correct
6 Correct 19 ms 37880 KB Output is correct
7 Correct 19 ms 37880 KB Output is correct
8 Correct 19 ms 37812 KB Output is correct
9 Correct 158 ms 81844 KB Output is correct
10 Correct 33 ms 45048 KB Output is correct
11 Correct 95 ms 62964 KB Output is correct
12 Correct 41 ms 47144 KB Output is correct
13 Correct 33 ms 43080 KB Output is correct
14 Correct 19 ms 37940 KB Output is correct
15 Correct 21 ms 38004 KB Output is correct
16 Correct 168 ms 81872 KB Output is correct
17 Incorrect 19 ms 40916 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -