#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
// const int MAXMEM = 200 * 1000 * 1024;
// char _memory[MAXMEM];
// size_t _ptr = 0;
// void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
// void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 100205;
int n;
int x[MAXN], y[MAXN];
vector<vector<int> > whox, whoy;
bool hor[MAXN], ver[MAXN];
int parent[MAXN];
int findset(int a) {
if (a == parent[a]) {
return a;
}
return parent[a] = findset(parent[a]);
}
void unite(int a, int b) {
a = findset(a);
b = findset(b);
if (a == b) {
return;
}
parent[a] = b;
}
int ss = 1;
vector<int> who[MAXN * 7];
struct node
{
int who = 0;
int cntalive = 0;
bool odnacomponenta = true;
};
node d[MAXN * 8];
node operator +(const node &a, const node &b) {
if (!a.cntalive) {
return b;
}
if (!b.cntalive) {
return a;
}
node c;
c.cntalive = a.cntalive + b.cntalive;
c.who = a.who;
c.odnacomponenta = a.odnacomponenta & b.odnacomponenta & (a.who == b.who);
return c;
}
void del(int i) {
i += ss;
d[i].cntalive = 0;
d[i].who = 0;
d[i].odnacomponenta = false;
while (i >> 1 > 0) {
i >>= 1;
d[i] = d[i * 2] + d[i * 2 + 1];
}
}
void change(int i, int comp) {
i += ss;
d[i].cntalive = 1;
d[i].who = comp;
d[i].odnacomponenta = true;
while (i >> 1 > 0) {
i >>= 1;
d[i] = d[i * 2] + d[i * 2 + 1];
}
}
int cur[MAXN * 2];
void tryunite(int v, int vl, int vr, int l, int r, int x) {
if (!d[v].cntalive) {
return;
}
if (vl > r || vr < l) {
return;
}
if (l <= vl && vr <= r) {
// cout << "opa" << ' ' << vl << ' ' << vr << endl;
if (d[v].odnacomponenta) {
// cout << "kek" << endl;
int t = findset(x);
if (t != x) {
int b= findset(d[v].who);
// cout << x << ' ' << t << ' ' << b << endl;
if (t != b) {
int g = sz(who[t]);
int g1 = sz(who[b]);
int a = t;
if (g < g1) {
swap(a, b);
}
parent[b] = a;
//cout << a << ' ' << b << endl;
for (auto x: who[b]) {
if (cur[x] != -1 && findset(cur[x]) == a) {
who[a].pb(x);
change(x, a);
}
}
who[b].clear();
who[b].shrink_to_fit();
}
} else {
parent[x] = findset(d[v].who);
}
} else {
tryunite(v * 2, vl, (vl + vr) / 2, l, r, x);
tryunite(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
}
return;
}
tryunite(v * 2, vl, (vl + vr) / 2, l, r, x);
tryunite(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
}
int valh[MAXN], valv[MAXN];
vector<pair<pair<int, int>, int> > fs[MAXN];
vector<pair<pair<int, int>, int> > mx[MAXN];
int cnt[MAXN][2];
int col[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// read(FILENAME);
cin >> n;
whox.resize(100001);
whoy.resize(100001);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
whox[x[i]].pb(i);
whoy[y[i]].pb(i);
parent[i] = i;
}
vector<pair<int, int> > vs, hs;
for (auto xx: whox) {
if (sz(xx) == 2) {
for (auto y: xx) {
ver[y] = true;
valv[y] = xx[0] ^ xx[1];
}
unite(xx[0], xx[1]);
if (y[xx[0]] > y[xx[1]]) {
swap(xx[0], xx[1]);
}
int t = findset(xx[0]);
fs[y[xx[0]]].pb({mp(x[xx[0]], t), 1});
fs[y[xx[1]]].pb({mp(x[xx[0]], t), -1});
}
}
for (auto xx: whoy) {
if (sz(xx) == 2) {
for (auto y: xx) {
hor[y] = true;
valh[y] = xx[0] ^ xx[1];
}
unite(xx[0], xx[1]);
int t = findset(xx[0]);
mx[y[xx[0]]].pb(mp(mp(x[xx[0]], x[xx[1]]), t));
}
}
for (int i = 0; i < n; i++) {
if (!ver[i] && !hor[i]) {
cout << "NE\n";
exit(0);
}
}
ss = 1;
while (ss <= 100000) {
ss <<= 1;
}
for (int i = 0; i <= 100000; i++) {
for (auto x: fs[i]) {
if (x.second == -1) {
// who[findset(cur[x.first.first])].erase(x.first.first);
cur[x.first.first] = -1;
del(x.first.first);
}
}
for (auto x: fs[i]) {
if (x.second == 1) {
cur[x.first.first] = x.first.second;
who[x.first.second].pb(x.first.first);
change(x.first.first, x.first.second);
}
}
for (auto x: mx[i]) {
int l = x.first.first;
int r = x.first.second;
if (l > r) {
swap(l, r);
}
tryunite(1, 1, ss, l + 1, r + 1, x.second);
}
}
for (int i = 0; i < n; i++) {
if (!ver[i]) {
cnt[findset(i)][1]++;
}
if (!hor[i]) {
cnt[findset(i)][0]++;
}
}
for (int i = 0; i < n; i++) {
if (findset(i) == i) {
if (cnt[i][0] && cnt[i][1]) {
cout << "NE\n";
return 0;
}
col[i] = cnt[i][0] ? 0: 1;
}
}
cout << "DA\n";
for (int i = 0; i < n; i++) {
int t = col[findset(i)];
int f = 0;
if (t == 0) {
f = valv[i] ^ i;
} else {
f = valh[i] ^ i;
}
if (f > i) {
assert(i != f);
cout << i + 1 << ' ' << f + 1 << '\n';
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
26496 KB |
Output is correct |
2 |
Correct |
20 ms |
26496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
26496 KB |
Output is correct |
2 |
Correct |
20 ms |
26496 KB |
Output is correct |
3 |
Correct |
20 ms |
26624 KB |
Output is correct |
4 |
Correct |
21 ms |
26624 KB |
Output is correct |
5 |
Correct |
20 ms |
26496 KB |
Output is correct |
6 |
Correct |
21 ms |
26496 KB |
Output is correct |
7 |
Correct |
20 ms |
26496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
26496 KB |
Output is correct |
2 |
Correct |
20 ms |
26496 KB |
Output is correct |
3 |
Correct |
20 ms |
26624 KB |
Output is correct |
4 |
Correct |
21 ms |
26624 KB |
Output is correct |
5 |
Correct |
20 ms |
26496 KB |
Output is correct |
6 |
Correct |
21 ms |
26496 KB |
Output is correct |
7 |
Correct |
20 ms |
26496 KB |
Output is correct |
8 |
Correct |
20 ms |
26752 KB |
Output is correct |
9 |
Correct |
20 ms |
26752 KB |
Output is correct |
10 |
Correct |
21 ms |
26704 KB |
Output is correct |
11 |
Correct |
21 ms |
26752 KB |
Output is correct |
12 |
Correct |
26 ms |
26672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
26496 KB |
Output is correct |
2 |
Correct |
20 ms |
26496 KB |
Output is correct |
3 |
Correct |
20 ms |
26624 KB |
Output is correct |
4 |
Correct |
21 ms |
26624 KB |
Output is correct |
5 |
Correct |
20 ms |
26496 KB |
Output is correct |
6 |
Correct |
21 ms |
26496 KB |
Output is correct |
7 |
Correct |
20 ms |
26496 KB |
Output is correct |
8 |
Correct |
20 ms |
26752 KB |
Output is correct |
9 |
Correct |
20 ms |
26752 KB |
Output is correct |
10 |
Correct |
21 ms |
26704 KB |
Output is correct |
11 |
Correct |
21 ms |
26752 KB |
Output is correct |
12 |
Correct |
26 ms |
26672 KB |
Output is correct |
13 |
Correct |
25 ms |
29312 KB |
Output is correct |
14 |
Correct |
29 ms |
29304 KB |
Output is correct |
15 |
Correct |
25 ms |
29312 KB |
Output is correct |
16 |
Correct |
24 ms |
29304 KB |
Output is correct |
17 |
Correct |
24 ms |
29184 KB |
Output is correct |
18 |
Correct |
24 ms |
29184 KB |
Output is correct |
19 |
Correct |
25 ms |
29184 KB |
Output is correct |
20 |
Correct |
24 ms |
29184 KB |
Output is correct |
21 |
Correct |
25 ms |
29184 KB |
Output is correct |
22 |
Correct |
24 ms |
29184 KB |
Output is correct |
23 |
Correct |
24 ms |
27896 KB |
Output is correct |
24 |
Correct |
23 ms |
27776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
26496 KB |
Output is correct |
2 |
Correct |
20 ms |
26496 KB |
Output is correct |
3 |
Correct |
20 ms |
26624 KB |
Output is correct |
4 |
Correct |
21 ms |
26624 KB |
Output is correct |
5 |
Correct |
20 ms |
26496 KB |
Output is correct |
6 |
Correct |
21 ms |
26496 KB |
Output is correct |
7 |
Correct |
20 ms |
26496 KB |
Output is correct |
8 |
Correct |
20 ms |
26752 KB |
Output is correct |
9 |
Correct |
20 ms |
26752 KB |
Output is correct |
10 |
Correct |
21 ms |
26704 KB |
Output is correct |
11 |
Correct |
21 ms |
26752 KB |
Output is correct |
12 |
Correct |
26 ms |
26672 KB |
Output is correct |
13 |
Correct |
25 ms |
29312 KB |
Output is correct |
14 |
Correct |
29 ms |
29304 KB |
Output is correct |
15 |
Correct |
25 ms |
29312 KB |
Output is correct |
16 |
Correct |
24 ms |
29304 KB |
Output is correct |
17 |
Correct |
24 ms |
29184 KB |
Output is correct |
18 |
Correct |
24 ms |
29184 KB |
Output is correct |
19 |
Correct |
25 ms |
29184 KB |
Output is correct |
20 |
Correct |
24 ms |
29184 KB |
Output is correct |
21 |
Correct |
25 ms |
29184 KB |
Output is correct |
22 |
Correct |
24 ms |
29184 KB |
Output is correct |
23 |
Correct |
24 ms |
27896 KB |
Output is correct |
24 |
Correct |
23 ms |
27776 KB |
Output is correct |
25 |
Correct |
160 ms |
40952 KB |
Output is correct |
26 |
Correct |
155 ms |
40952 KB |
Output is correct |
27 |
Correct |
153 ms |
40952 KB |
Output is correct |
28 |
Correct |
164 ms |
40960 KB |
Output is correct |
29 |
Correct |
146 ms |
40312 KB |
Output is correct |
30 |
Correct |
146 ms |
40312 KB |
Output is correct |
31 |
Correct |
145 ms |
40184 KB |
Output is correct |
32 |
Correct |
148 ms |
40312 KB |
Output is correct |
33 |
Correct |
133 ms |
39160 KB |
Output is correct |
34 |
Correct |
150 ms |
39324 KB |
Output is correct |
35 |
Correct |
93 ms |
34936 KB |
Output is correct |
36 |
Execution timed out |
2578 ms |
38992 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |