#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
p getParent(p cur, vvp &dsuParent)
{
if (dsuParent[cur.f][cur.s] == cur) return cur;
return dsuParent[cur.f][cur.s] = getParent(dsuParent[cur.f][cur.s], dsuParent);
}
vp getNeighbors(p pos, ll maxX, ll maxY)
{
vp neighbors; ll i = pos.f; ll j = pos.s;
if (i - 1 >= 0)
{
neighbors.eb(i - 1, j);
}
if (i + 1 < maxX)
{
neighbors.eb(i + 1, j);
}
if (j - 1 >= 0)
{
neighbors.eb(i, j - 1);
}
if (j + 1 < maxY)
{
neighbors.eb(i, j + 1);
}
return neighbors;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, t;
cin >> n >> t;
vp cells(n);
for (ll i= 0; i < n; i++) cin >> cells[i].f >> cells[i].s;
v relevantX, relevantY;
for (ll i = 0; i < n; i++)
{
relevantX.pb(cells[i].f - 1);
relevantX.pb(cells[i].f);
relevantX.pb(cells[i].f + 1);
relevantY.pb(cells[i].s - 1);
relevantY.pb(cells[i].s);
relevantY.pb(cells[i].s + 1);
}
sort(all(relevantX)); sort(all(relevantY));
relevantX.erase(unique(all(relevantX)), relevantX.end()); relevantY.erase(unique(all(relevantY)), relevantY.end());
map<ll, ll> xShrink;
map<ll, ll> yShrink;
for (ll i = 0; i < relevantX.size(); i++) xShrink[relevantX[i]] = i + 1;
for (ll i = 0; i < relevantY.size(); i++) yShrink[relevantY[i]] = i + 1;
for (ll i = 0; i < n; i++) cells[i] = p(xShrink[cells[i].f], yShrink[cells[i].s]);
ll maxX = relevantX.size() + 2, maxY = relevantY.size() + 2;
vv occupied(maxX, v(maxY, -1));
for (ll i = 0; i < n; i++) occupied[cells[i].f][cells[i].s] = i;
set<ll> remaining;
deque<ll> available;
set<ll> avSet;
for (ll i = 0; i < n; i++) remaining.insert(i);
v order;
vb possible(n, false);
vv adjacentStructures(n);
for (ll i = 0; i < n; i++)
{
for (ll j = i + 1; j < n; j++)
{
if (abs(cells[i].f - cells[j].f) <= 1 && abs(cells[i].s - cells[j].s) <= 1)
{
adjacentStructures[i].pb(j);
adjacentStructures[j].pb(i);
}
}
}
vb visited(n, false);
stack<ll> dfs; dfs.push(0);
ll cnt = 0;
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (visited[top]) continue;
visited[top] = true; cnt++;
for (ll x : adjacentStructures[top]) dfs.push(x);
}
if (cnt != n)
{
cout << "NO\n";
return 0;
}
vvp dsuParent(maxX, vp(maxY));
for (ll i = 0; i < maxX; i++) for (ll j = 0; j < maxY; j++) dsuParent[i][j] = p(i, j);
vv dsuSize(maxX, v(maxY, 1));
for (ll i = 0; i < maxX; i++)
{
for (ll j = 0; j < maxY; j++)
{
if (occupied[i][j] != -1) continue;
vp neighbors = getNeighbors(p(i, j), maxX, maxY);
for (auto x : neighbors)
{
if (occupied[x.f][x.s] != -1) continue;
p p1 = getParent(p(i, j), dsuParent), p2 = getParent(x, dsuParent);
if (p1 == p2) continue;
if (dsuSize[p1.f][p1.s] > dsuSize[p2.f][p2.s]) swap(p1,p2);
dsuParent[p1.f][p1.s] = p2;
dsuSize[p2.f][p2.s] += dsuSize[p1.f][p1.s];
}
}
}
for (ll i = 0; i < n; i++)
{
vp neighbors = getNeighbors(cells[i], maxX, maxY);
bool hasNeighbor = false;
p expected = getParent(p(0, 0), dsuParent);
for (auto y : neighbors)
{
if (getParent(y, dsuParent) == expected) hasNeighbor = true;
}
if (hasNeighbor && avSet.count(i) == 0)
{
available.pf(i);
avSet.insert(i);
}
}
for (ll i = n - 1; i >= 0; i--)
{
bool done = false;
for (ll j = 0; j < available.size(); j++)
{
ll x = available[j];
vp neighbors = getNeighbors(cells[x], maxX, maxY);
if (i > 1)
{
vb visited(n, false);
auto ptr = remaining.begin();
if (*ptr == x) ptr++;
ll start = *ptr;
stack<ll> dfs; dfs.push(start);
ll cnt = 0;
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (remaining.count(top) == 0 || top == x || visited[top]) continue;
visited[top] = true; cnt++;
for (ll x : adjacentStructures[top]) dfs.push(x);
}
if (cnt != remaining.size() - 1)
{
continue;
}
}
occupied[cells[x].f][cells[x].s] = -1;
for (auto y : neighbors)
{
if (occupied[y.f][y.s] == -1)
{
p p1 = getParent(y, dsuParent), p2 = getParent(cells[x], dsuParent);
if (p1 == p2) continue;
if (dsuSize[p1.f][p1.s] > dsuSize[p2.f][p2.s]) swap(p1,p2);
dsuParent[p1.f][p1.s] = p2;
dsuSize[p2.f][p2.s] += dsuSize[p1.f][p1.s];
}
}
p expect = getParent(p(0, 0), dsuParent);
p par = getParent(cells[x], dsuParent);
if (par == expect)
{
for (auto y : neighbors)
{
if (occupied[y.f][y.s] == -1)
{
vp nei = getNeighbors(y, maxX, maxY);
for (auto z : nei)
{
if (occupied[z.f][z.s] != -1 && avSet.count(occupied[z.f][z.s]) == 0)
{
available.pf(occupied[z.f][z.s]);
avSet.insert(occupied[z.f][z.s]);
}
}
}
else if (avSet.count(occupied[y.f][y.s]) == 0)
{
available.pf(occupied[y.f][y.s]);
avSet.insert(occupied[y.f][y.s]);
}
}
}
remaining.erase(x);
available.erase(available.begin() + j);
order.pb(x);
done = true;
break;
}
assert(done);
}
reverse(all(order));
cout << "YES\n";
for (ll x : order) cout << x + 1 << "\n";
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:80:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (ll i = 0; i < relevantX.size(); i++) xShrink[relevantX[i]] = i + 1;
| ~~^~~~~~~~~~~~~~~~~~
skyscrapers.cpp:81:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (ll i = 0; i < relevantY.size(); i++) yShrink[relevantY[i]] = i + 1;
| ~~^~~~~~~~~~~~~~~~~~
skyscrapers.cpp:158:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for (ll j = 0; j < available.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~
skyscrapers.cpp:178:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | if (cnt != remaining.size() - 1)
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
344 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 5 |
Incorrect |
1 ms |
344 KB |
Full cells must be connected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
344 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 5 |
Incorrect |
1 ms |
344 KB |
Full cells must be connected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
344 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 5 |
Incorrect |
1 ms |
344 KB |
Full cells must be connected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
114 ms |
265300 KB |
ans=NO N=1934 |
| 2 |
Correct |
4 ms |
860 KB |
ans=NO N=1965 |
| 3 |
Execution timed out |
3591 ms |
824 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
344 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 5 |
Incorrect |
1 ms |
344 KB |
Full cells must be connected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2758 ms |
15836 KB |
ans=NO N=66151 |
| 2 |
Correct |
2503 ms |
17848 KB |
ans=NO N=64333 |
| 3 |
Execution timed out |
3522 ms |
20412 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
114 ms |
265300 KB |
ans=NO N=1934 |
| 2 |
Correct |
4 ms |
860 KB |
ans=NO N=1965 |
| 3 |
Execution timed out |
3591 ms |
824 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
