#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 100000 + 10;
const int maxl = 200;
struct point{
int x, y;
} p[maxn];
struct segment{
point a;
point b;
int i1, i2;
segment(){
i1 = i2 = -1;
}
} s[maxn];
vector<int> vex[maxn], vey[maxn], vec[maxn], add[maxn], del[maxn];
int ask[maxn], cnt;
int lc[maxn * maxl], rc[maxn * maxl];
vector<int> g[maxn * maxl][2];
bool light[maxn][2];
int cmp[maxn * maxl], comp;
bool visited[maxn * maxl];
vector<int> topol;
void dfs(int v, bool w){
visited[v] = 1;
for (auto u : g[v][w])
if (!visited[u])
dfs(u, w);
if (w == 0)
topol.push_back(v);
else
cmp[v] = comp;
}
void scc(){
int n = cnt;
for (int i = 0; i < n; i++)
if (!visited[i])
dfs(i, 0);
reverse(topol.begin(), topol.end());
memset(visited, 0, sizeof visited);
for (auto i : topol){
if (!visited[i]){
dfs(i, 1);
comp ++;
}
}
}
void add_edge(int v, int u, bool type){ // type = 0 : v -> u, else v <- u
if (type == 1)
swap(v, u);
// cout << "edge : " << v << " -> " << u << endl;
g[v][0].push_back(u);
g[u][1].push_back(v);
}
void get(int id, int L, int R, int l, int r, int v, bool type){
if (r <= L or R <= l)
return;
if (l <= L and R <= r){
add_edge(v, id, type);
return;
}
int mid = (L + R) >> 1;
get(lc[id], L, mid, l, r, v, type);
get(rc[id], mid, R, l, r, v, type);
}
int change(int id, int L, int R, int idx, int v, bool type){
if (idx < L or R <= idx)
return id;
int me = cnt ++;
if (L + 1 == R){
if (light[L][type] == 1)
return me;
add_edge(me, v, type);
light[L][type] = 1;
return me;
}
int mid = (L + R) >> 1;
lc[me] = change(lc[id], L, mid, idx, v, type);
rc[me] = change(rc[id], mid, R, idx, v, type);
add_edge(me, lc[me], type), add_edge(me, rc[me], type);
return me;
}
int build(int L, int R, bool type){
int me = cnt ++;
if (L + 1 == R)
return me;
int mid = (L + R) >> 1;
lc[me] = build(L, mid, type);
rc[me] = build(mid, R, type);
add_edge(me, lc[me], type), add_edge(me, rc[me], type);
return me;
}
int main(){
ios_base::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> p[i].x >> p[i].y;
vex[p[i].x].push_back(i);
vey[p[i].y].push_back(i);
}
int newint = 0;
int N = 100000 + 1;
for (int i = 1; i < N; i++){
if (vex[i].size() == 2){
segment me;
me.a = p[vex[i][0]];
me.b = p[vex[i][1]];
me.i1 = vex[i][0];
me.i2 = vex[i][1];
vec[me.i1].push_back(newint);
vec[me.i2].push_back(newint);
s[newint++] = me;
}
if (vey[i].size() == 2){
segment me;
me.a = p[vey[i][0]];
me.b = p[vey[i][1]];
me.i1 = vey[i][0];
me.i2 = vey[i][1];
vec[me.i1].push_back(newint);
vec[me.i2].push_back(newint);
s[newint++] = me;
}
}
int m = newint;
memset(ask, -1, sizeof ask);
for (int i = 0; i < m; i++){
if (s[i].a.x != s[i].b.x){
if (s[i].a.x > s[i].b.x){
swap(s[i].a, s[i].b);
swap(s[i].i1, s[i].i2);
}
add[s[i].a.x].push_back(i);
add[s[i].b.x].push_back(i);
}
else
ask[s[i].a.x] = i;
}
for (int i = 0; i < n; i++){
if ((int)vec[i].size() == 0)
return cout << "NE\n", 0;
if ((int)vec[i].size() == 1){
int v = vec[i][0];
add_edge(2*v+1, 2*v+0, 0);
continue;
}
int v = vec[i][0], u = vec[i][1];
add_edge(2*v+1, 2*u+0, 0);
add_edge(2*u+1, 2*v+0, 0);
add_edge(2*v+0, 2*u+1, 0);
add_edge(2*u+0, 2*v+1, 0);
}
// for (int i = 0; i < m; i++)
// cout << "# " << i << " -> (" << s[i].a.x << " , " << s[i].a.y << ") - (" << s[i].b.x << " , " << s[i].b.y << ")" << endl;
cnt = 2*m;
int r1 = build(1, N, 0);
int r2 = build(1, N, 1);
for (int i = 1; i < N; i++){
if (ask[i] != -1){
int idx = ask[i];
int y1 = s[idx].a.y, y2 = s[idx].b.y;
if (y1 > y2)
swap(y1, y2);
get(r1, 1, N, y1+1, y2, 2*idx+0, 0);
get(r2, 1, N, y1+1, y2, 2*idx+1, 1);
// cout << "Ask : " << idx << " : " << y1+1 << " - " << y2 << endl;
}
for (auto idx : add[i]){
// cout << "Add or Remove : " << idx << " - " << s[idx].a.y << endl;
r1 = change(r1, 1, N, s[idx].a.y, 2*idx+1, 0);
r2 = change(r2, 1, N, s[idx].a.y, 2*idx+0, 1);
}
}
scc();
for (int i = 0; i < 2*m; i+=2)
if (cmp[i] == cmp[i+1])
return cout << "NE\n", 0;
cout << "DA\n";
for (int i = 0; i < m; i++)
if (cmp[2*i+0] > cmp[2*i+1])
cout << s[i].i1 + 1 << " " << s[i].i2 + 1 << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
