#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int MAXN = 1e5 + 5;
const int offset = 1 << 17;
struct Node {
int val;
Node* nxt;
};
class Graph {
Node* get_node(int dest, Node* head) {
Node* newNode = new Node;
newNode -> val = dest;
newNode -> nxt = head;
return newNode;
}
int N;
public:
Node **head;
Graph(int N) {
head = new Node*[N]();
this -> N = N;
for (int i = 0; i < N; i++)
head[i] = nullptr;
}
Graph(){}
void add(int src, int dest) {
head[src] = get_node(dest, head[src]);
}
~Graph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
int n;
stack <int> order;
vector <pii> edges;
inline int add_variables(int vars) {
n += vars;
return n - vars;
}
void add_edge(int u, int v) {
edges.push_back({u, v});
}
void add_implication(int u1, int neg1, int u2, int neg2) {
if (u1 == -1 || u2 == -1)
return;
add_edge(2 * u1 + neg1, 2 * u2 + neg2);
add_edge(2 * u2 + !neg2, 2 * u1 + !neg1);
}
void dfs_forward(int x, Graph &g, char *vis) {
vis[x] = 1;
for (Node* ptr = g.head[x]; ptr != nullptr; ptr = ptr -> nxt)
if (!vis[ptr -> val])
dfs_forward(ptr -> val, g, vis);
order.push(x);
}
void bye() {
puts("NE");
exit(0);
}
void dfs_backward(int x, Graph &g, char *vis, bool *ans) {
if (vis[x ^ 1] == -1)
bye();
vis[x] = -1;
ans[x] = vis[x ^ 1];
for (Node* ptr = g.head[x]; ptr != nullptr; ptr = ptr -> nxt)
if (!vis[ptr -> val])
dfs_backward(ptr -> val, g, vis, ans);
vis[x] = 1;
}
int N;
int x[MAXN], y[MAXN];
int off[2 * offset];
vector <int> pos[2 * offset];
vector <pii> tour[2 * offset];
vector <int> hor[MAXN], ver[MAXN];
unordered_map <int, pii> segs;
vector <int> graph[MAXN];
void load() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d%d", x + i, y + i);
hor[y[i]].push_back(i);
ver[x[i]].push_back(i);
}
}
void insert(int x, int lo, int hi, int from, int to, int var, int height) {
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
tour[x].push_back({height, var});
return;
}
int mid = (lo + hi) / 2;
insert(2 * x, lo, mid, from, to, var, height);
insert(2 * x + 1, mid, hi, from, to, var, height);
}
inline int get_id(int node, int x) {
return x >= off[node] && x < off[node] + tour[node].size() ? tour[node][x - off[node]].second : pos[node][x];
}
void add_clause(int x, int u, int v) {
add_implication(get_id(x, u), 0, get_id(x, v), 0);
}
bool dfs(int node, int x, vector <int> &v) {
if (x >= off[node])
return x < off[node] + tour[node].size();
dfs(node, 2 * x, v);
if (dfs(node, 2 * x + 1, v)) {
v.push_back(x);
return true;
}
return false;
}
void init(int x) {
if (tour[x].empty())
return;
off[x] = 1;
sort(tour[x].begin(), tour[x].end());
while (off[x] < tour[x].size())
off[x] *= 2;
vector <int> toAdd;
dfs(x, 1, toAdd);
int sz = toAdd.size();
int st = add_variables(sz);
pos[x].resize(2 * off[x], -1);
for (int i = 0; i < sz; i++)
pos[x][toAdd[i]] = st + i;
for (auto it : toAdd) {
add_clause(x, 2 * it, it);
add_clause(x, 2 * it + 1, it);
}
}
int get_bounds(int x, int val) {
int lo = 0, hi = tour[x].size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tour[x][mid].first >= val)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
void update(int node, int from, int to, int var) {
if (!off[node])
return;
from += off[node];
to += off[node];
while (from < to) {
if (from % 2)
add_implication(get_id(node, from++), 0, var, 1);
if (to % 2)
add_implication(get_id(node, --to), 0, var, 1);
from /= 2;
to /= 2;
}
}
void add_intersections(int x, int down, int up, int var) {
for (x += offset; x; x /= 2)
update(x, get_bounds(x, down), get_bounds(x, up + 1), var);
}
void two_sat() {
bool *sol = new bool[2 * n];
char *bio = new char[2 * n];
Graph adj(2 * n), rev(2 * n);
for (auto it : edges) {
adj.add(it.first, it.second);
rev.add(it.second, it.first);
}
for (int i = 0; i < 2 * n; i++)
if (!bio[i])
dfs_forward(i, adj, bio);
for (int i = 0; i < 2 * n; i++)
bio[i] = 0;
for (; !order.empty(); order.pop())
if (!bio[order.top()])
dfs_backward(order.top(), rev, bio, sol);
puts("DA");
for (auto it : segs)
if (sol[2 * it.first])
printf("%d %d\n", it.second.first + 1, it.second.second + 1);
delete[] sol;
delete[] bio;
}
void solve() {
for (int i = 1; i < MAXN; i++)
if (hor[i].size() == 2) {
int tmp = add_variables(1);
segs[tmp] = {hor[i][0], hor[i][1]};
int l = MAXN, r = 0;
for (auto it : hor[i]) {
graph[it].push_back(tmp);
l = min(l, x[it]);
r = max(r, x[it]);
}
insert(1, 0, offset, l, r + 1, tmp, i);
}
for (int i = 0; i < 2 * offset; i++)
init(i);
for (int i = 1; i < MAXN; i++)
if (ver[i].size() == 2) {
int tmp = add_variables(1);
segs[tmp] = {ver[i][0], ver[i][1]};
int l = MAXN, r = 0;
for (auto it : ver[i]) {
graph[it].push_back(tmp);
l = min(l, y[it]);
r = max(r, y[it]);
}
add_intersections(i, l, r, tmp);
}
for (int i = 0; i < N; i++)
if (!graph[i].empty())
add_implication(graph[i][0], 1, graph[i][1 % graph[i].size()], 0);
else
bye();
two_sat();
}
int main() {
double timer = clock();
load();
solve();
fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
return 0;
}
Compilation message
matching.cpp: In function 'int get_id(int, int)':
matching.cpp:116:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return x >= off[node] && x < off[node] + tour[node].size() ? tour[node][x - off[node]].second : pos[node][x];
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'bool dfs(int, int, std::vector<int>&)':
matching.cpp:125:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return x < off[node] + tour[node].size();
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'void init(int)':
matching.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (off[x] < tour[x].size())
~~~~~~~^~~~~~~~~~~~~~~~
matching.cpp: In function 'void load()':
matching.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
matching.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", x + i, y + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19968 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
19 ms |
19840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19968 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
19 ms |
19840 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
19968 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19968 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
19 ms |
19840 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
19968 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
18 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19968 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
19 ms |
19840 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
19968 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
