#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
const int N = 20;
int r[N], c[N], used[N], is[N][N];
int tin[N], fup[N], ap[N], on[N];
int near[N];
vector<int> edges[N];
int ch[8][2] = {
{1, 0},
{0, 1},
{0, -1},
{-1, 0},
{-1, -1},
{-1, 1},
{1, -1},
{1, 1}
};
void dfs(int u){
used[u] = 1;
for(auto x : edges[u]){
if(used[x]) continue;
dfs(x);
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, t; cin>>n>>t;
map<ar<int, 2>, int> mm;
int r_ = 1e9, c_ = 1e9;
for(int i=0;i<n;i++){
cin>>r[i]>>c[i];
r_ = min(r_, r[i]);
c_ = min(c_, c[i]);
for(int t=0;t<8;t++){
int x = r[i] + ch[t][0], y = c[i] + ch[t][1];
if(mm.count({x, y})){
x = mm[{x, y}];
edges[x].push_back(i);
edges[i].push_back(x);
}
}
mm[{r[i], c[i]}] = i;
}
mm.clear();
for(int i=0;i<n;i++){
r[i] = r[i] - r_ + (r_ > 0);
c[i] = c[i] - c_ + (c_ > 0);
mm[{r[i], c[i]}] = i;
//~ cout<<r[i]<<" "<<c[i]<<endl;
}
dfs(0);
//~ for(int i=0;i<n;i++){
//~ cout<<used[i]<<" ";
//~ } cout<<endl;
for(int i=0;i<n;i++){
if(!used[i]){
cout<<"NO\n";
return 0;
}
}
//~ vector<int> mn(n, N);
int cmp = 1;
function<void(int, int)> dfs2 = [&](int i, int j){
is[i][j] = cmp;
//~ cout<<i<<" "<<j<<endl;
for(int t=0;t<4;t++){
int x = i + ch[t][0], y = j + ch[t][1];
if(mm.count({x, y})){
if(cmp == 1){
int k = mm[{x, y}];
near[k] = 1;
}
} else if(~x && x < N && ~y && y < N && !is[x][y]){
//~ cout<<" -> "<<x<<" "<<y<<endl;
dfs2(x, y);
}
}
};
for(int i=0;i<N;i++){
if(!is[i][N-1]) dfs2(i, N - 1);
if(!is[N-1][i]) dfs2(N - 1, i);
} cmp++;
for(int i=N-2;~i;i--){
for(int j=N-2;~j;j--){
if(is[i][j] || mm.count({i, j})) continue;
dfs2(i, j), cmp++;
}
}
int tim = 0;
function<void(int, int)> dfs3 = [&](int u, int p){
tin[u] = fup[u] = ++tim;
used[u] = 1;
int c = 0, cnt = 0;
for(auto x : edges[u]){
if(x == p || on[x]) continue;
if(used[x]){
fup[u] = min(fup[u], tin[x]);
c = 1;
} else {
cnt++;
dfs3(x, u);
fup[u] = min(fup[u], fup[x]);
}
}
if(tin[u] > fup[u]){
ap[u] = 0;
} else {
if(c || cnt == 0) ap[u] = 0;
else if(p == u && cnt == 1) ap[u] = 0;
else ap[u] = 1;
}
};
//~ cout<<"here"<<endl;
vector<int> res;
for(int i=0;i<n;i++){
memset(used, 0, sizeof used);
tim = 0;
for(int i=0;i<n;i++){
if(on[i]) continue;
dfs3(i, i); break;
}
int v = -1;
for(int i=0;i<n;i++){
if(ap[i] || on[i]) continue;
if(near[i]) v = i;
}
if(v == -1){
cout<<"NO\n";
return 0;
}
on[v] = 1;
vector<int> tmp;
for(int t=0;t<4;t++){
int x = r[v] + ch[t][0], y = c[v] + ch[t][1];
if(is[x][y] > 1) tmp.push_back(is[x][y]);
}
for(int i=0;i<n;i++){
if(on[i]) continue;
for(int t=0;t<4;t++){
int x = r[i] + ch[t][0], y = c[i] + ch[t][1];
for(auto e : tmp){
if(is[x][y] == e){
is[x][y] = 1;
near[i] = 1;
break;
}
}
}
}
res.push_back(v);
}
cout<<"YES\n";
for(auto x : res) cout<<++ x<<" ";
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ans=YES N=1 |
| 2 |
Incorrect |
1 ms |
340 KB |
Contestant did not find solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ans=YES N=1 |
| 2 |
Incorrect |
1 ms |
340 KB |
Contestant did not find solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ans=YES N=1 |
| 2 |
Incorrect |
1 ms |
340 KB |
Contestant did not find solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ans=YES N=1 |
| 2 |
Incorrect |
1 ms |
340 KB |
Contestant did not find solution |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
