#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXM = 1e6;
int N, M, M1, M2;
pii A[MAXN+10];
vector<int> X[MAXN+10], Y[MAXN+10];
int P[MAXN+10], Q[MAXN+10];
pii E[MAXN+10];
vector<int> adj[MAXM+10], radj[MAXM+10];
bool vis[MAXM+10];
vector<int> S;
void dfs(int now)
{
vis[now]=true;
for(int nxt : adj[now])
{
if(vis[nxt]) continue;
dfs(nxt);
}
S.push_back(now);
}
int scc[MAXM+10], scnt;
void dfs2(int now)
{
scc[now]=scnt;
for(int nxt : radj[now])
{
if(scc[nxt]) continue;
dfs2(nxt);
}
}
void addEdge(int u, int v)
{
if(u==0 || v==0) return;
//printf("%d %d\n", u, v);
adj[u].push_back(v);
radj[v].push_back(u);
}
pii nodes[MAXM+10];
int update(int node, int tl, int tr, int p, int k)
{
if(p<tl || tr<p) return node;
int ret=++M;
if(tl==tr)
{
addEdge(ret, k);
return ret;
}
int mid=tl+tr>>1;
nodes[ret]={update(nodes[node].first, tl, mid, p, k), update(nodes[node].second, mid+1, tr, p, k)};
addEdge(ret, nodes[ret].first);
addEdge(ret, nodes[ret].second);
return ret;
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++)
{
scanf("%d%d", &A[i].first, &A[i].second);
X[A[i].first].push_back(i);
Y[A[i].second].push_back(i);
}
for(int i=1; i<=MAXN; i++)
{
if(X[i].size()==2)
{
M++;
if(X[i][0]>X[i][1]) swap(X[i][0], X[i][1]);
E[M]={X[i][0], X[i][1]};
P[X[i][0]]=M;
P[X[i][1]]=M;
}
}
M1=M;
for(int i=1; i<=MAXN; i++)
{
if(Y[i].size()==2)
{
M++;
if(Y[i][0]>Y[i][1]) swap(Y[i][0], Y[i][1]);
E[M]={Y[i][0], Y[i][1]};
Q[Y[i][0]]=M;
Q[Y[i][1]]=M;
}
}
M2=M;
for(int i=1; i<=N; i++)
{
if(P[i]==0 && Q[i]==0)
{
return !printf("NE\n");
}
if(P[i] && Q[i])
{
addEdge(P[i]+M2, Q[i]);
addEdge(P[i], Q[i]+M2);
addEdge(Q[i]+M2, P[i]);
addEdge(Q[i], P[i]+M2);
}
else if(P[i])
{
addEdge(P[i]+M2, P[i]);
}
else if(Q[i])
{
addEdge(Q[i]+M2, Q[i]);
}
}
M*=2;
for(int i=1; i<=M1; i++) for(int j=M1+1; j<=M2; j++)
{
if(A[E[i].first].second<=A[E[j].first].second && A[E[j].second].second<=A[E[i].second].second)
{
if(A[E[j].first].first<=A[E[i].first].first && A[E[i].second].first<=A[E[j].second].first)
{
addEdge(i, j+M2);
addEdge(j, i+M2);
}
}
}
/*
vector<pii> V;
for(int i=1; i<=M1; i++)
{
V.push_back({A[E[i].first].second, i});
V.push_back({A[E[i].second].second+1, -i});
}
for(int i=M1+1; i<=M2; i++)
{
V.push_back({A[E[i].first].second, i});
}
sort(V.begin(), V.end());
int root=++M;
for(auto it : V)
{
if(it.second>=M1+1)
{
addEdge(it.second, root);
}
else
{
if(it.second>=0)
{
root=update(root, 1, MAXN, A[it.second].first, it.second+M2);
}
else
{
root=update(root, 1, MAXN, A[-it.second].first, 0);
}
}
}
V.clear();
for(int i=M1+1; i<=M2; i++)
{
V.push_back({A[E[i].first].first, i});
V.push_back({A[E[i].second].first+1, -i});
}
for(int i=1; i<=M1; i++)
{
V.push_back({A[E[i].first].first, i+M2});
}
sort(V.begin(), V.end());
root=++M;
for(auto it : V)
{
if(it.second>=M2+1)
{
addEdge(it.second-M2, root);
}
else
{
if(it.second>=0)
{
root=update(root, 1, MAXN, A[it.second].second, it.second+M2);
}
else
{
root=update(root, 1, MAXN, A[-it.second].second, 0);
}
}
}
*/
for(int i=1; i<=M; i++) if(!vis[i]) dfs(i);
reverse(S.begin(), S.end());
for(auto it : S)
{
if(scc[it]) continue;
scnt++;
dfs2(it);
}
for(int i=1; i<=M2; i++)
{
//printf("%d %d\n", E[i].first, E[i].second);
printf("%d %d\n", scc[i], scc[i+M2]);
if(scc[i]==scc[i+M2]) return !printf("NE\n");
}
printf("DA\n");
for(int i=1; i<=M2; i++)
{
if(scc[i]>scc[i+M2]) printf("%d %d\n", E[i].first, E[i].second);
}
}
Compilation message
matching.cpp: In function 'int update(int, int, int, int, int)':
matching.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid=tl+tr>>1;
| ~~^~~
matching.cpp: In function 'int main()':
matching.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
matching.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d%d", &A[i].first, &A[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
56684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
