Submission #112152

#	Time	Username	Problem	Language	Result	Execution time	Memory
112152		dolphingarlic	Konj (COCI19_konj)	C++14	56 / 70	209 ms	19196 KiB

konj

#include <bits/stdc++.h>
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#pragma GCC optimize("O3")
typedef long long ll;
using namespace std;

struct Point {
	int x;
	int y;
};

vector<pair<int, Point>> endpoints[301][301];
vector<pair<int, pair<Point, Point>>> lines;
bool grid[301][301];
bool visited[200001];

int mx_x = 0, mx_y = 0, mn_x = 301, mn_y = 301;

void dfs(int x, int y) {
	mx_x = max(mx_x, x);
	mx_y = max(mx_y, y);
	mn_x = min(mn_x, x);
	mn_y = min(mn_y, y);
	for (auto& i : endpoints[x][y]) {
		if (!visited[i.first]) {
			visited[i.first] = true;
			if (i.second.x == x) {
				FOR(j, min(y, i.second.y), max(y, i.second.y) + 1) {
					grid[j][x] = true;
				}
			} else {
				FOR(j, min(x, i.second.x), max(x, i.second.x) + 1) {
					grid[y][j] = true;
				}
			}
			dfs(i.second.x, i.second.y);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	fill(visited, visited + n, false);
	FOR(i, 0, 301) {
		fill(grid[i], grid[i] + 301, false);
	}

	FOR(i, 0, n) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		endpoints[a][b].push_back({i, {c, d}});
		endpoints[c][d].push_back({i, {a, b}});
		lines.push_back({i, {{a, b}, {c, d}}});
	}
	int a, b;
	cin >> a >> b;

	FOR(i, 0, 301) {
		for (auto& i : lines) {
			if ((i.second.first.x == i.second.second.x && b <= max(i.second.first.y, i.second.second.y) && b >= min(i.second.first.y, i.second.second.y)) ||
				(i.second.first.y == i.second.second.y && a <= max(i.second.first.x, i.second.second.x) && b >= min(i.second.first.x, i.second.second.x))) {
				visited[i.first] = true;
				if (i.second.first.x == i.second.second.x) {
					FOR(j, min(i.second.first.y, i.second.second.y), max(i.second.first.y, i.second.second.y) + 1) {
						grid[j][i.second.first.x] = true;
					}
				} else {
					FOR(j, min(i.second.first.x, i.second.second.x), max(i.second.first.x, i.second.second.x) + 1) {
						grid[i.second.first.y][j] = true;
					}
				}
				dfs(i.second.first.x, i.second.first.y);
				dfs(i.second.second.x, i.second.second.y);
			}
		}
	}

	for (int i = mx_y; i >= mn_y; i--) {
		FOR(j, mn_x, mx_x + 1) {
			cout << (grid[i][j] ? '#' : '.');
		}
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 56 / 70