Submission #334938

#TimeUsernameProblemLanguageResultExecution timeMemory
334938ronnithKonj (COCI19_konj)C++14
70 / 70
162 ms17516 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...