#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const vector<int> dxa = { 0, 1, 0, -1 };
const vector<int> dya = { 1, 0, -1, 0 };
class disjoint_set {
private:
int N;
vector<int> par;
public:
disjoint_set() : N(0), par() {};
disjoint_set(int N_) : N(N_), par(N_) {
for(int i = 0; i < N_; ++i) {
par[i] = i;
}
}
int root(int x) {
if(par[x] == x) return x;
return par[x] = root(par[x]);
}
void link(int x, int y) {
par[root(x)] = root(y);
}
bool connected(int x, int y) {
return root(x) == root(y);
}
};
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int N, T;
cin >> N >> T;
vector<int> X(N), Y(N);
for(int i = 0; i < N; ++i) {
cin >> X[i] >> Y[i];
}
int xl = *min_element(X.begin(), X.end());
int yl = *min_element(Y.begin(), Y.end());
for(int i = 0; i < N; ++i) {
X[i] -= xl - 1;
Y[i] -= yl - 1;
}
int H = *max_element(X.begin(), X.end()) + 2;
int W = *max_element(Y.begin(), Y.end()) + 2;
vector<vector<int> > G(N);
for(int i = 0; i < N; ++i) {
for(int j = i + 1; j < N; ++j) {
int d = max(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
if(d == 1) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
vector<bool> vis_ini(N);
function<void(int)> dfs_ini = [&](int pos) {
vis_ini[pos] = true;
for(int i : G[pos]) {
if(!vis_ini[i]) {
dfs_ini(i);
}
}
};
dfs_ini(0);
if(vis_ini != vector<bool>(N, true)) {
cout << "NO" << endl;
}
else {
vector<vector<bool> > building(H, vector<bool>(W, false));
for(int i = 0; i < N; ++i) {
building[X[i]][Y[i]] = true;
}
disjoint_set uf(H * W);
for(int i = 0; i < H; ++i) {
for(int j = 0; j < W; ++j) {
if(building[i][j]) continue;
for(int k = 0; k < 4; ++k) {
int tx = i + dxa[k], ty = j + dya[k];
if(0 <= tx && tx < H && 0 <= ty && ty < W && !building[tx][ty]) {
uf.link(i * W + j, tx * W + ty);
}
}
}
}
vector<bool> used(N, false);
vector<int> seq;
for(int i = 0; i < N; ++i) {
vector<bool> vis(N);
function<void(int)> dfs = [&](int pos) {
vis[pos] = true;
for(int j : G[pos]) {
if(!vis[j] && !used[j]) {
dfs(j);
}
}
};
for(int j = 0; j < N; ++j) {
if(used[j]) continue;
used[j] = true;
int comps = 0;
vis = vector<bool>(N, false);
for(int k = 0; k < N; ++k) {
if(!used[k] && !vis[k]) {
dfs(k);
++comps;
}
}
bool ok = false;
for(int k = 0; k < 4; ++k) {
int tx = X[j] + dxa[k], ty = Y[j] + dya[k];
if(uf.connected(0, tx * W + ty)) ok = true;
}
if(comps <= 1 && ok) {
seq.push_back(j);
for(int k = 0; k < 4; ++k) {
int tx = X[j] + dxa[k], ty = Y[j] + dya[k];
if(!building[tx][ty]) {
uf.link(X[j] * W + Y[j], tx * W + ty);
}
}
break;
}
used[j] = false;
building[X[j]][Y[j]] = false;
}
}
reverse(seq.begin(), seq.end());
cout << "YES" << '\n';
for(int i = 0; i < N; ++i) {
cout << seq[i] + 1 << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
384 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
384 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
384 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
384 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
384 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
384 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
384 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 10 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 11 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 12 |
Correct |
1 ms |
512 KB |
ans=YES N=9 |
| 13 |
Correct |
1 ms |
384 KB |
ans=YES N=9 |
| 14 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 15 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 16 |
Correct |
0 ms |
384 KB |
ans=NO N=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
384 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
384 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
384 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
384 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
384 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
384 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
384 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 10 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 11 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 12 |
Correct |
1 ms |
512 KB |
ans=YES N=9 |
| 13 |
Correct |
1 ms |
384 KB |
ans=YES N=9 |
| 14 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 15 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 16 |
Correct |
0 ms |
384 KB |
ans=NO N=2 |
| 17 |
Correct |
0 ms |
384 KB |
ans=YES N=17 |
| 18 |
Correct |
0 ms |
384 KB |
ans=YES N=25 |
| 19 |
Incorrect |
2 ms |
384 KB |
Added cell 58 (1,-1) not reachable from infinity |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
384 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
384 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
384 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
384 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
384 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
384 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
384 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 10 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 11 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 12 |
Correct |
1 ms |
512 KB |
ans=YES N=9 |
| 13 |
Correct |
1 ms |
384 KB |
ans=YES N=9 |
| 14 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 15 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 16 |
Correct |
0 ms |
384 KB |
ans=NO N=2 |
| 17 |
Correct |
0 ms |
384 KB |
ans=YES N=17 |
| 18 |
Correct |
0 ms |
384 KB |
ans=YES N=25 |
| 19 |
Incorrect |
2 ms |
384 KB |
Added cell 58 (1,-1) not reachable from infinity |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
ans=NO N=1934 |
| 2 |
Correct |
8 ms |
512 KB |
ans=NO N=1965 |
| 3 |
Execution timed out |
3565 ms |
640 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
384 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
384 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
384 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
384 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
384 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
384 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
384 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 10 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 11 |
Correct |
0 ms |
384 KB |
ans=YES N=10 |
| 12 |
Correct |
1 ms |
512 KB |
ans=YES N=9 |
| 13 |
Correct |
1 ms |
384 KB |
ans=YES N=9 |
| 14 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 15 |
Correct |
0 ms |
384 KB |
ans=YES N=8 |
| 16 |
Correct |
0 ms |
384 KB |
ans=NO N=2 |
| 17 |
Correct |
0 ms |
384 KB |
ans=YES N=17 |
| 18 |
Correct |
0 ms |
384 KB |
ans=YES N=25 |
| 19 |
Incorrect |
2 ms |
384 KB |
Added cell 58 (1,-1) not reachable from infinity |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3578 ms |
4468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
ans=NO N=1934 |
| 2 |
Correct |
8 ms |
512 KB |
ans=NO N=1965 |
| 3 |
Execution timed out |
3565 ms |
640 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
