제출 #1167822

#제출 시각아이디문제언어결과실행 시간메모리
1167822FedShatMatching (COCI20_matching)C++20
58 / 110
2595 ms23560 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> g; vector<int> clr; int clrs = 0; vector<int> st; vector<bool> inSt; int t; vector<int> up; void dfs(int v){ int tin = t++; up[v] = tin; st.push_back(v); inSt[v] = true; for(int u : g[v]){ if(clr[u] == -1 && !inSt[u]){ dfs(u); } if(inSt[u]){ up[v] = min(up[v], up[u]); } } if(up[v] == tin){ while(st.back() != v){ int u = st.back(); st.pop_back(); inSt[u] = false; clr[u] = clrs; } inSt[v] = false; clr[v] = clrs; st.pop_back(); clrs++; } } vector<pair<int, int>> points; struct line{ int x1, y1, x2, y2; int ind1, ind2; line(int ind1_, int ind2_){ ind1 = ind1_; ind2 = ind2_; x1 = points[ind1].first; x2 = points[ind2].first; y1 = points[ind1].second; y2 = points[ind2].second; if(x1 > x2) swap(x1, x2); if(y1 > y2) swap(y1, y2); } }; bool check(line hor, line vert){ return hor.x1 < vert.x1 && vert.x1 < hor.x2 && vert.y1 < hor.y1 && hor.y1 < vert.y2; } int vertvertices; void preparesat(int vert_, int hor_){ g.resize((vert_ + hor_) * 2); vertvertices = vert_; } int vertical(int v){ return v * 2; } int nvertical(int v){ return v * 2 + 1; } int gorizontal(int v){ return vertvertices * 2 + v * 2; } int ngorizontal(int v){ return vertvertices * 2 + v * 2 + 1; } void solve(){ int n; cin >> n; points.resize(n); vector<pair<int, int>> lines(n, {-1, -1}); unordered_map<int, int> vert; unordered_map<int, int> hor; vector<line> vertlines; vector<line> horlines; for(int i = 0; i < n; i++){ int x, y; cin >> x >> y; points[i].first = x; points[i].second = y; if(vert.find(x) != vert.end()){ int j = vert[x]; lines[i].first = vertlines.size(); lines[j].first = vertlines.size(); vertlines.push_back(line(i, j)); }else{ vert[x] = i; } if(hor.find(y) != hor.end()){ int j = hor[y]; lines[i].second = horlines.size(); lines[j].second = horlines.size(); horlines.push_back(line(i, j)); }else{ hor[y] = i; } } preparesat(vertlines.size(), horlines.size()); for(int i = 0; i < n; i++){ if(lines[i].first == -1 && lines[i].second == -1){ cout << "NE\n"; return; }else if(lines[i].first == -1){ int v = gorizontal(lines[i].second); g[v + 1].push_back(v); }else if(lines[i].second == -1){ int v = vertical(lines[i].first); g[v + 1].push_back(v); }else{ int v = vertical(lines[i].first); int u = gorizontal(lines[i].second); g[u].push_back(v + 1); g[u + 1].push_back(v); g[v].push_back(u + 1); g[v + 1].push_back(u); } } for(int i = 0; i < horlines.size(); i++){ for(int j = 0; j < vertlines.size(); j++){ if(check(horlines[i], vertlines[j])){ int v = gorizontal(i); int u = vertical(j); g[v].push_back(u + 1); g[u].push_back(v + 1); } } } int w = g.size(); inSt.assign(w, false); clr.assign(w, -1); up.assign(w, -1); for(int i = 0; i < w; i++){ if(clr[i] == -1){ dfs(i); } } vector<pair<int, int>> ans; for(int i = 0; i < vertlines.size(); i++){ int v = vertical(i); if(clr[v] == clr[v + 1]){ cout << "NE\n"; return; }else if(clr[v] < clr[v + 1]){ ans.push_back({vertlines[i].ind1, vertlines[i].ind2}); } } for(int i = 0; i < horlines.size(); i++){ int v = gorizontal(i); if(clr[v] == clr[v + 1]){ cout << "NE\n"; return; }else if(clr[v] < clr[v + 1]){ ans.push_back({horlines[i].ind1, horlines[i].ind2}); } } cout << "DA\n"; for(auto [a, b] : ans){ cout << a + 1 << ' ' << b + 1 << '\n'; } } signed main(){ #ifdef LOCAL freopen("D:\\projects\\olymp\\input.txt", "r", stdin); freopen("D:\\projects\\olymp\\output.txt", "w", stdout); #endif int t = 1; // cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...