Submission #197050

#	Time	Username	Problem	Language	Result	Execution time	Memory
197050		Vlatko	Konj (COCI19_konj)	C++14	49 / 70	74 ms	8824 KiB

konj

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;
const int M = 301;

struct DSU {
	int p[N], rank[N];
	DSU() {
		for (int i = 0; i < N; ++i) {
			p[i] = i;
			rank[i] = 0;
		}
	}
	inline int get(int x) { 
		return p[x] == x ? x : (p[x] = get(p[x]));
	}
	inline bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) swap(x, y);
		if (rank[x] == rank[y]) ++rank[x];
		p[y] = x;
		return true;
	}
} dsu;

int n, tx, ty, minx, miny, maxx, maxy;
int segs[N][4];
bool good[N];
int endp[M][M];
int dx[M][M], dy[M][M];
bool black[M][M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(endp, -1, sizeof(endp));
	memset(dx, 0, sizeof(dx));
	memset(dy, 0, sizeof(dy));
	memset(black, false, sizeof(black));
	minx = miny = M;
	maxx = maxy = -1;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		segs[i][0] = a, segs[i][1] = b;
		segs[i][2] = c, segs[i][3] = d;
		if (endp[a][b] != -1) {
			dsu.unite(i, endp[a][b]);
		} else {
			endp[a][b] = i;
		}
		if (endp[c][d] != -1) {
			dsu.unite(i, endp[c][d]);
		} else {
			endp[c][d] = i;
		}
		good[i] = false;
	}
	cin >> tx >> ty;
	for (int i = 0; i < n; ++i) {
		int a = segs[i][0], b = segs[i][1];
		int c = segs[i][2], d = segs[i][3];
		int j = dsu.get(i);
		if (a == c ? (b <= ty && ty <= d) : (a <= tx && tx <= c)) {
			good[j] = true;
		}
		if (good[j]) {
			minx = min(minx, min(a, c));
			maxx = max(maxx, max(a, c));
			miny = min(miny, min(b, d));
			maxy = max(maxy, max(b, d));
		}
	}
	for (int i = 0; i < n; ++i) {
		int &a = segs[i][0], &b = segs[i][1];
		int &c = segs[i][2], &d = segs[i][3];
		int j = dsu.get(i);
		if (good[j]) {
			if (a > c) swap(a, c);
			if (b > d) swap(b, d);
			if (a == c) {
				dy[a][b] += 1, dy[a][d+1] -= 1;
			} else {
				dx[a][b] += 1, dx[c+1][b] -= 1;
			}
		}
	}
	for (int x = minx; x <= maxx; ++x) {
		int s = 0;
		for (int y = miny; y <= maxy; ++y) {
			s += dy[x][y];
			if (s > 0) black[x][y] = true;
		}
	}
	for (int y = miny; y <= maxy; ++y) {
		int s = 0;
		for (int x = miny; x <= maxx; ++x) {
			s += dx[x][y];
			if (s > 0) black[x][y] = true;
		}
	}
	for (int y = maxy; y >= miny; --y) {
		for (int x = minx; x <= maxx; ++x) {
			cout << (black[x][y] ? '#' : '.');
		}
		cout << '\n';
	}
}

• Subtask 1: 49 / 70