#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,+1},{+1,+1},{+1,0},{+1,-1},{0,-1}};
int dv[4][2] = {{-1,0},{+1,0},{0,+1},{0,-1}};
const int N = 151169;
const int M = (int)4e6;
pii vv[M];
set<int> Q[M];
int par[M];
map<pii,int> indx;
map<pii,int> emp;
map<pii,int> vis;
int deg[N];
int xi[N], yi[N];
int cnt = 0;
void dfs(pii cur){
cnt ++ ;
vis[cur]=true;
pii go;
for(int p = 0 ; p < 8 ; p ++ ){
go = mp(cur.fi+dir[p][0],cur.se+dir[p][1]);
if(indx.count(go) && !vis[go]){
dfs(go);
}
}
}
pii low = mp((int)1e9 + 7, (int)1e9 + 7);
int fin(int x){
if(par[x]==x) return x;
return par[x]=fin(par[x]);
}
void unite(int u, int v){
u=fin(u);
v=fin(v);
if(u==v) return;
if(Q[u].size() > Q[v].size()) swap(u,v);
for(auto x : Q[u]){
Q[v].insert(x);
}
Q[u].clear();
par[u]=v;
}
bool can_remove(pii yi){
vector<int> c;
pii nx;
for(int d = 0; d < 8 ; d ++ ){
nx = mp(yi.fi + dir[d][0], yi.se + dir[d][1]);
if(!emp.count(nx)) c.push_back(-1);
else c.push_back(fin(emp[nx]));
}
int cnt = 0;
for(auto x : c) if(x == -1) cnt ++ ; // full cells
if(cnt >= 7 || cnt <= 1) return true;
int p, q;
for(int i = 0 ; i < 8; i += 2 ){
q = (i + 1) % 8;
p = (i - 1 + 8) % 8;
if(c[p] >= 0 && c[p] == c[q]){ // cut off
return false;
}
}
if(c[1] >= 0 && c[1] == c[5] && min({c[0],c[7],c[6]}) == -1 && min({c[2],c[5],c[4]}) == -1){
return false;
}
if(c[7] >= 0 && c[7] == c[3] && min({c[0],c[1],c[2]}) == -1 && min({c[4],c[5],c[6]}) == -1){
return false;
}
return true;
}
int main(){
fastIO;
int n, typ;
cin >> n >> typ;
for(int i = 1; i <= n; i ++ ){
cin >> xi[i] >> yi[i];
indx[mp(xi[i],yi[i])]=i;
}
pii nx;
int id=0;
for(int i = 1;i <= n; i ++ ){
for(int d = 0; d < 8 ; d ++ ){
nx = mp(xi[i]+dir[d][0],yi[i]+dir[d][1]);
if(indx.count(nx)){
deg[i]++;
continue;
}
if(!emp.count(nx)){
emp[nx]=id;
vv[id]=nx;
par[id]=id;
id++;
}
Q[emp[nx]].insert(i);
}
}
for(int i = 0 ; i < id; i ++ ){
low = min(low, vv[i]);
for(int j = 0 ; j < 4; j ++ ){
nx = mp(vv[i].fi+dv[j][0], vv[i].se+dv[j][1]);
if(emp.count(nx)){
unite(i,emp[nx]);
}
}
}
dfs(mp(xi[1],yi[1]));
if(cnt != n){
cout << "NO\n";
return 0;
}
vector<int> ord;
int cid;
cout << "YES\n";
set<int> bad;
int idx;
for(int i = 0 ; i < n; i ++ ){
cid = fin(emp[low]);
while(!Q[cid].empty()){
auto it = Q[cid].end();
-- it;
if(can_remove(mp(xi[*it],yi[*it]))){
idx = *it;
ord.push_back(idx);
Q[cid].erase(idx);
indx[mp(xi[idx],yi[idx])]=0;
par[id]=id;
vv[id]=mp(xi[idx],yi[idx]);
emp[mp(xi[idx],yi[idx])]=id;
for(int d = 0 ; d < 8 ; d ++ ){
nx = mp(xi[idx]+dir[d][0], yi[idx]+dir[d][1]);
if(indx[nx]>0){
Q[id].insert(indx[nx]);
deg[indx[nx]]--;
if(deg[indx[nx]] <= 1 && bad.count(indx[nx])){
bad.erase(indx[nx]);
Q[cid].insert(indx[nx]);
}
}
}
for(int d = 0; d < 8 ; d ++ ){
nx = mp(xi[idx]+dir[d][0],yi[idx]+dir[d][1]);
if(emp.count(nx)){
unite(id,emp[nx]);
}
}
id ++ ;
break;
}
else{
bad.insert(*it);
Q[cid].erase(it);
}
}
}
reverse(ord.begin(),ord.end());
for(auto yy : ord){
cout << yy << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188268 KB |
ans=YES N=1 |
| 2 |
Incorrect |
127 ms |
188168 KB |
Unexpected end of file - int32 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188268 KB |
ans=YES N=1 |
| 2 |
Incorrect |
127 ms |
188168 KB |
Unexpected end of file - int32 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188268 KB |
ans=YES N=1 |
| 2 |
Incorrect |
127 ms |
188168 KB |
Unexpected end of file - int32 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
190444 KB |
ans=NO N=1934 |
| 2 |
Correct |
136 ms |
189220 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
162 ms |
188908 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
188268 KB |
ans=YES N=1 |
| 2 |
Incorrect |
127 ms |
188168 KB |
Unexpected end of file - int32 expected |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
748 ms |
214380 KB |
ans=NO N=66151 |
| 2 |
Correct |
1472 ms |
245228 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
992 ms |
211292 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
190444 KB |
ans=NO N=1934 |
| 2 |
Correct |
136 ms |
189220 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
162 ms |
188908 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
