Submission #334938

#	Time	Username	Problem	Language	Result	Execution time	Memory
334938		ronnith	Konj (COCI19_konj)	C++14	70 / 70	162 ms	17516 KiB

konj

#include <bits/stdc++.h>
#define trav(a, b) for(auto a : b)
#define mk make_pair
#define f first
#define s second
#define vi vector<int>
#define pb push_back

using namespace std;

struct Line{
	int x1, y1;
	int x2, y2;
	Line(){}
	Line(int a, int b, int c, int d){
		x1 = a;
		y1 = b;
		x2 = c;
		y2 = d;
	}
};

struct DSU{
	int cnt;vi e;DSU(int N){cnt = N;e = vi(N,-1);}
	int root(int x){return (e[x] < 0) ? x : e[x] = root(e[x]);}
	bool same(int x,int y){return root(x) == root(y);}
	void unite(int x,int y){
		x = root(x), y = root(y);if(x == y)return;
		if(e[y] < e[x])swap(x,y);
		e[x] += e[y];
		e[y] = x;
		cnt --;
	}
};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	map<pair<int, int>, vector<int>> mp;
	vector<Line> arr(n);
	for(int i = 0;i < n;i ++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		mp[mk(a,b)].pb(i + 1);
		mp[mk(c,d)].pb(i + 1);
		arr[i] = Line(a, b, c, d);
	}
	int x, y;cin >> x >> y;
	mp[mk(x,y)].pb(0);
	DSU d(n + 1);
	trav(e, mp){
		int prev = -1;
		trav(a, e.s){
			if(prev != -1){
				d.unite(prev, a);
			}
			prev = a;
		}
	}
	for(int i = 0;i < n;i ++){
		auto e = arr[i];
		if(e.x1 == e.x2 and x == e.x1 and y <= max(e.y1, e.y2) and y >= min(e.y1, e.y2)){
			d.unite(0, i + 1);
		}
		if(e.y1 == e.y2 and y == e.y1 and x <= max(e.x1, e.x2) and x >= min(e.x1, e.x2)){
			d.unite(0, i + 1);
		}
	}
	vector<int> final;
	for(int i = 0;i < n;i ++){
		if(d.same(0, i + 1)){
			final.pb(i);
		}
	}
	int mx = INT_MIN;
	int mn = INT_MAX;
	int MX = INT_MIN;
	int MN = INT_MAX;
	trav(e, final){
		mx = max(mx, arr[e].x1);
		mn = min(mn, arr[e].x1);
		mx = max(mx, arr[e].x2);
		mn = min(mn, arr[e].x2);

		MX = max(MX, arr[e].y1);
		MN = min(MN, arr[e].y1);
		MX = max(MX, arr[e].y2);
		MN = min(MN, arr[e].y2);
	}
	// cerr << MX << " " << MN << '\n';
	// cerr << mx << " " << mn << '\n';
	char ans[MX - MN + 1][mx - mn + 1];
	for(int i = 0;i < MX - MN + 1;i ++){
		for(int j = 0;j < mx - mn + 1;j ++){
			ans[i][j] = '.';
		}
	}
	trav(h, final){
		auto e = arr[h];
		if(e.x1 == e.x2){
			for(int i = min(e.y1, e.y2);i <= max(e.y1, e.y2);i ++){
				ans[i - MN][e.x1 - mn] = '#';
			}
		} else {
			for(int i = min(e.x1, e.x2);i <= max(e.x1, e.x2);i ++){
				ans[e.y1 - MN][i - mn] = '#';
			}
		}
	}
	for(int i = MX - MN;i >= 0;i --){
		for(int j = 0;j < mx - mn + 1;j ++){
			cout << ans[i][j];
		}
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 70 / 70