#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
const int maxn = 150001;
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int inv[] = {4, 5, 6, 7, 0, 1, 2, 3};
struct cell;
int n, t, ID;
cell* Find (cell *x);
void check (cell *c);
void Union (cell *a, cell *b);
map<pair<int,int>, cell*> cells;
struct cell {
bool full, out;
int x, y, ind;
cell* adj[8], *parent = this, *prev = nullptr;
vector<cell*> vec;
cell(int a, int b, bool f) {
// cerr << endl << a << " " << b << endl;
full = f;
x = a, y = b;
cells[{x, y}] = this;
if (f == 0) vec = {this};
else ind = ID;
for (int d = 0 ; d < 8 ; d++) {
int u = x + dx[d];
int v = y + dy[d];
auto it = cells.find({u, v});
if (it != cells.end()) {
adj[d] = it -> second;
it -> second -> adj[inv[d]] = this;
}
else adj[d] = nullptr;
}
if (f == 0) {
for (int d = 0 ; d < 8 ; d += 2) {
if (adj[d]) {
if (!adj[d] -> full) Union(this, adj[d]);
}
}
for (int d = 0 ; d < 8 ; d += 2) {
if (adj[d] and adj[d] -> full) check(adj[d]);
}
}
}
};
cell* inp[maxn];
struct cmp {
bool operator () (cell *a, cell *b) const {
return a -> ind > b -> ind;
}
};
set<cell*,cmp> expendable;
cell* Find (cell *x) {
return x == x -> parent ? x : x -> parent = Find(x -> parent);
}
void check (cell *c) {
bool articulation = 0, isout = 0, sep = 0;
for (int i = 0 ; i < 8 ; i++) {
if (!c -> adj[i]) return;
if (!c -> adj[i] -> full) isout |= Find(c -> adj[i]) -> out;
}
if (!isout) {
expendable.erase(c);
return;
}
for (int _d = 0 ; _d < 9 ; _d++) {
int d = (_d == 8 ? 0 : _d);
if (c -> adj[d] -> full) {
sep = 1;
continue;
}
if (d & 1) continue;
auto cmp = Find(c -> adj[d]);
if (cmp -> prev and sep == 1) {
bool bad = 0;
for (int __d = _d ; !bad ; __d++) {
int d2 = __d % 8;
if (c -> adj[d2] == cmp -> prev) break;
if (c -> adj[d2] -> full) bad = 1;
}
if (bad) articulation = 1;
}
cmp -> prev = c -> adj[d];
sep = 0;
}
for (int d = 0 ; d < 8 ; d++) {
if (!c -> adj[d] -> full) Find(c -> adj[d]) -> prev = nullptr;
}
// cerr << c -> x << " " << c -> y << " " << isout << " " << (bool)articulation << endl;
if (isout and !articulation) expendable.insert(c);
else expendable.erase(c);
}
void Union (cell *a, cell *b) {
cell *x = Find(a), *y = Find(b);
if (x == y) return;
if (x -> vec.size() > y -> vec.size()) swap(x, y);
x -> parent = y;
y -> out |= x -> out;
for (auto &i : x -> vec) {
for (int d = 0 ; d < 8 ; d++) if (i -> adj[d] and i -> adj[d] -> full) check(i -> adj[d]);
y -> vec.push_back(i);
}
x -> vec.clear();
}
signed main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> t;
for (int i = 0 ; i < n ; i++) {
ID = i;
int x, y;
cin >> x >> y;
inp[i] = new cell(x, y, 1);
}
int idx = 0;
for (int i = 0 ; i < n ; i++) {
if (inp[i] -> x < inp[idx] -> x) idx = i;
else if (inp[i] -> x == inp[idx] -> x and inp[i] -> y < inp[idx] -> y) idx = i;
}
inp[idx] -> adj[4] = new cell(inp[idx] -> x + dx[4], inp[idx] -> y + dy[4], 0);
inp[idx] -> adj[4] -> out = 1;
// cerr << idx << endl;
for (int i = 0 ; i < n ; i++) {
// cerr << i << ": ";
for (int d = 0 ; d < 8 ; d++) {
// cerr << d << " ";
if (!inp[i] -> adj[d]) {
inp[i] -> adj[d] = new cell(inp[i] -> x + dx[d], inp[i] -> y + dy[d], 0);
}
}
}
// assert(0);
if (n > 1) {
for (int i = 0 ; i < n ; i++) {
bool good = 0;
for (int d = 0 ; d < 8 ; d++) {
if (inp[i] -> adj[d] -> full) good = 1;
}
if (!good) {
cout << "NO\n";
return 0;
}
}
}
for (int i = 0 ; i < n ; i++) check(inp[i]);
cout << "YES\n";
vector<int> ans;
while (expendable.size()) {
auto cur = *expendable.begin();
check(cur);
if (*expendable.begin() != cur) continue;
expendable.erase(expendable.begin());
ans.push_back(cur -> ind + 1);
*cur = cell(cur -> x, cur -> y, 0);
}
reverse(ans.begin(), ans.end());
for (int i: ans) cout << i << endl;
}
Compilation message
election.cpp:17:1: warning: multi-line comment [-Wcomment]
17 | //\
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
3540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
